fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define debug     cout << "ok\n";
  4. #define SQR(x)    (1LL * ((x) * (x)))
  5. #define MASK(i)   (1LL << (i))
  6. #define BIT(x, i) (((x) >> (i)) & 1)
  7. #define fi        first
  8. #define se        second
  9. #define pb        push_back
  10.  
  11. #define mp make_pair
  12. #define pii pair<int,int>
  13. #define pli pair<ll,int>
  14. #define vi vector<int>
  15.  
  16. #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  17.  
  18. typedef long long ll;
  19. typedef unsigned long long ull;
  20. typedef long double ld;
  21. typedef unsigned int ui;
  22.  
  23. using namespace std;
  24.  
  25. const int M = 1e9 + 7;
  26. const int INF = 1e9 + 7;
  27. const ll INFLL = (ll)2e18 + 7LL;
  28. const ld PI = acos(-1);
  29.  
  30. const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  31. const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  32.  
  33. template<class _, class __>
  34.     bool minimize(_ &x, const __ y){
  35.         if(x > y){
  36.             x = y;
  37.             return true;
  38.         } else return false;
  39.     }
  40. template<class _, class __>
  41.     bool maximize(_ &x, const __ y){
  42.         if(x < y){
  43.             x = y;
  44.             return true;
  45.         } else return false;
  46.     }
  47.  
  48. template<class _,class __>
  49.     void Add(_ &x, const __ y) {
  50.         x += y;
  51.         if (x >= M) {
  52.             x -= M;
  53.         }
  54.         return;
  55.     }
  56.  
  57. template<class _,class __>
  58.     void Diff(_ &x, const __ y) {
  59.         x -= y;
  60.         if (x < 0) {
  61.             x += M;
  62.         }
  63.         return;
  64.     }
  65.  
  66. //--------------------------------------------------------------
  67.  
  68. const int MaxN = 1e6+7;
  69.  
  70. int n,m,a[MaxN];
  71.  
  72. namespace sub1 {
  73.     bool check() {
  74.         return n <= 500;
  75.     }
  76.  
  77.     bool _ch(int a,int b) {
  78.         if (a > b) b += n;
  79.         return (b - a)*2 < n;
  80.     }
  81.  
  82.     bool ch(int a,int b,int c) {
  83.         if (_ch(a,b) && _ch(b,c) && _ch(c,a)) return true;
  84.     }
  85.  
  86.     void sol() {
  87.         int res = 0;
  88.         for (int i=1;i<=m;i++) {
  89.             for (int j=i+1;j<=m;j++) {
  90.                 for (int k=j+1;k<=m;k++) {
  91.                     res += ch(a[i],a[j],a[k]);
  92. //                    if (ch(a[i],a[j],a[k])) cout << a[i] << ' ' << a[j] << ' ' << a[k] << '\n';
  93.                 }
  94.             }
  95.         }
  96.         cout << res;
  97.     }
  98. }
  99.  
  100. namespace sub2 {
  101.     bool check() {
  102.         return n <= 5000;
  103.     }
  104.  
  105.     int sum[10007];
  106.     bool ch[10007];
  107.  
  108.     void sol() {
  109.         for (int i=1;i<=m;i++) {
  110.             for (int j=0;j<=1;j++) {
  111.                 sum[a[i] + j*n]++;
  112.                 ch[a[i] + j*n] = true;
  113.             }
  114.         }
  115.         for (int i=1;i<=2*n;i++) sum[i] += sum[i-1];
  116.         ll res = 0;
  117.         for (int i=1;i<=n;i++) {
  118.             for (int j=1;2*j < n;j++) {
  119.                 int k = i + j;
  120.                 if (!ch[i] || !ch[k]) continue;
  121.                 int l = i + n/2 + 1;
  122.                 int r = k + (n+1)/2 - 1;
  123.                 if (l <= r) {
  124.                     res += sum[r] - sum[l-1];
  125.                 }
  126.             }
  127.         }
  128.         cout << res/3;
  129.     }
  130. }
  131.  
  132. namespace sub3 {
  133.     bool check() {
  134.         return n == m;
  135.     }
  136.  
  137.     ll C(int n,int k) {
  138.         ll res = 1;
  139.         for (int i=n-k+1;i<=n;i++) res *= i;
  140.         for (int i=1;i<=k;i++) res /= i;
  141.         return res;
  142.     }
  143.  
  144.     void sol() {
  145.         ll res = C(n,3);
  146.         res -= 1LL*n*C(n/2,2);
  147.         cout << res;
  148.     }
  149. }
  150.  
  151. namespace sub4 {
  152.     bool check() {
  153.         return true;
  154.     }
  155.  
  156.     int sum[MaxN*2];
  157.     bool ch[MaxN*2];
  158.  
  159.     ll C(int n,int k) {
  160.         ll res = 1;
  161.         for (int i=n-k+1;i<=n;i++) res *= i;
  162.         for (int i=1;i<=k;i++) res /= i;
  163.         return res;
  164.     }
  165.  
  166.     void sol() {
  167.         for (int i=1;i<=m;i++) {
  168.             for (int j=0;j<=1;j++) {
  169.                 sum[a[i] + j*n]++;
  170.                 ch[a[i] + j*n] = true;
  171.             }
  172.         }
  173.         for (int i=1;i<=2*n;i++) sum[i] += sum[i-1];
  174.         ll res = 0;
  175.         for (int i=1;i<=n;i++) {
  176.             if (!ch[i]) continue;
  177.             int r = i + n - 1;
  178.             int l = i + (n+1)/2;
  179.             res += C(sum[r] - sum[l-1],2);
  180.         }
  181.         res = C(m,3) - res;
  182.         cout << res;
  183.     }
  184. }
  185.  
  186. void sol() {
  187.     cin >> n >> m;
  188.     for (int i=1;i<=m;i++) {
  189.         cin >> a[i];
  190.     }
  191.     sort(a+1,a+m+1);
  192.     if (sub1::check()) {
  193.         sub1::sol();
  194.         return;
  195.     }
  196.     if (sub2::check()) {
  197.         sub2::sol();
  198.         return;
  199.     }
  200.     if (sub3::check()) {
  201.         sub3::sol();
  202.         return;
  203.     }
  204.     if (sub4::check()) {
  205.         sub4::sol();
  206.         return;
  207.     }
  208. }
  209.  
  210. int main() {
  211. 	freopen("TRI.INP","r",stdin);
  212. 	freopen("TRI.OUT","w",stdout);
  213. 	FAST
  214. 	int t=1;
  215. //	cin >> t;
  216. 	while (t--) sol();
  217. }
  218.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/RW9yvg
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!