fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
  5. #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
  6. #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
  7.  
  8. #define ALL(v)   (v).begin(), (v).end()
  9. #define fi   first
  10. #define se   second
  11.  
  12. #define MASK(i) (1LL << (i))
  13. #define BIT(x, i) (((x) >> (i)) & 1)
  14.  
  15. template<class X, class Y>
  16.     bool minimize(X &x, const Y &y) {
  17.         if (x > y) {
  18.             x = y;
  19.             return true;
  20.         } else return false;
  21.     }
  22.  
  23. template<class X, class Y>
  24.     bool maximize(X &x, const Y &y) {
  25.         if (x < y) {
  26.             x = y;
  27.             return true;
  28.         } else return false;
  29.     }
  30.  
  31. struct SegmentTree {
  32.     vector<int> minValue, minCount, lazy;
  33.     int n;
  34.  
  35.     void build(int i, int l, int r) {
  36.         minCount[i] = r - l + 1;
  37.         if (l == r) return;
  38.         int m = (l + r) >> 1;
  39.         build(2 * i, l, m);
  40.         build(2 * i + 1, m + 1, r);
  41.     }
  42.  
  43.     SegmentTree(int _n = 0) {
  44.         n = _n;
  45.         minValue.assign(4 * n + 7, 0);
  46.         minCount.assign(4 * n + 7, 0);
  47.         lazy.assign(4 * n + 7, 0);
  48.         build(1, 1, n);
  49.     }
  50.  
  51.     void pushDown(int i) {
  52.         if (lazy[i] == 0) return;
  53.         FOR(j, 2 * i, 2 * i + 1) {
  54.             minValue[j] += lazy[i];
  55.             lazy[j] += lazy[i];
  56.         }
  57.         lazy[i] = 0;
  58.     }
  59.  
  60.     void update(int i, int l, int r, int u, int v, int c) {
  61.         if (l > v || r < u || l > r || v < u) return;
  62.         if (u <= l && r <= v) {
  63.             minValue[i] += c;
  64.             lazy[i] += c;
  65.             return;
  66.         }
  67.  
  68.         pushDown(i);
  69.         int m = (l + r) >> 1;
  70.         update(2 * i, l, m, u, v, c);
  71.         update(2 * i + 1, m + 1, r, u, v, c);
  72.         minValue[i] = min(minValue[2 * i], minValue[2 * i + 1]);
  73.         minCount[i] = (minValue[2 * i] == minValue[i] ? minCount[2 * i] : 0) + (minValue[2 * i + 1] == minValue[i] ? minCount[2 * i + 1] : 0);
  74.     }
  75.  
  76.     void update(int l, int r, int c) {
  77.         update(1, 1, n, l, r, c);
  78.     }
  79.  
  80.     int getNumZero(void) const {
  81.         return minValue[1] == 0 ? minCount[1] : 0;
  82.     }
  83. };
  84.  
  85. struct Update {
  86.     int fr, to, delta;
  87.  
  88.     Update(int _fr = 0, int _to = 0, int _delta = 0) {
  89.         fr = _fr; to = _to; delta = _delta;
  90.     }
  91. };
  92.  
  93. #define MAX   100100
  94. int n, m, a[MAX];
  95.  
  96. void init(void) {
  97.     scanf("%d%d", &n, &m);
  98.     FOR(i, 1, n) scanf("%d", &a[i]);
  99. }
  100.  
  101. namespace subtask1 {
  102.     int cnt[MAX], cntOfCnt[MAX];
  103.  
  104.     bool check(void) {
  105.         return n <= 1000;
  106.     }
  107.  
  108.     void process(void) {
  109.         int res = 0;
  110.         FOR(l, 1, n) {
  111.             memset(cnt, 0, (n + 1) * sizeof (int));
  112.             memset(cntOfCnt, 0, (n + 1) * sizeof (int));
  113.             cntOfCnt[0] = n;
  114.  
  115.             FOR(r, l, n) {
  116.                 cntOfCnt[cnt[a[r]]]--;
  117.                 cnt[a[r]]++;
  118.                 cntOfCnt[cnt[a[r]]]++;
  119.  
  120.                 bool ok = true;
  121.                 FOR(i, 1, m) if (cntOfCnt[i] == 0) ok = false;
  122.                 if (ok) res++;
  123.             }
  124.         }
  125.  
  126.         printf("%d\n", res);
  127.     }
  128. }
  129.  
  130. namespace subtask2 {
  131.     bool check(void) {
  132.         FOR(i, 1, n) if (a[i] > m) return false;
  133.         return true;
  134.     }
  135.  
  136.     int cnt[10], have[10];
  137.  
  138.     void process(void) {
  139.         int res = 0;
  140.         FOR(i, 1, n) if (i + m * (m + 1) / 2 - 1 <= n) {
  141.             int j = i + m * (m + 1) / 2 - 1;
  142.             memset(cnt, 0, sizeof cnt);
  143.             memset(have, 0, sizeof have);
  144.             FOR(k, i, j) cnt[a[k]]++;
  145.             FOR(k, 1, m) have[cnt[k]]++;
  146.  
  147.             bool ok = true;
  148.             FOR(k, 1, m) if (have[k] == 0) ok = false;
  149.             if (ok) res++;
  150.         }
  151.         printf("%d\n", res);
  152.     }
  153. }
  154.  
  155. namespace subtask4 {
  156.     bool check(void) {
  157.         return true;
  158.     }
  159.  
  160.     vector<int> pos[MAX];
  161.     vector<Update> updates[5][MAX];
  162.  
  163.     void addRectangle(int id, int minX, int maxX, int minY, int maxY) {
  164.         updates[id][minX].push_back(Update(minY, maxY, +1));
  165.         updates[id][maxX + 1].push_back(Update(minY, maxY, -1));
  166.     }
  167.  
  168.     void prepare(void) {
  169.         FOR(i, 1, n) pos[a[i]].push_back(i);
  170.         FOR(i, 1, n) {
  171.             vector<int> &v = pos[i];
  172.             v.insert(v.begin(), 0);
  173.             v.push_back(n + 1);
  174.  
  175.             FOR(j, 1, v.size() - 2) REP(k, m) if (j + k <= (int)v.size() - 2)
  176.                 addRectangle(k + 1, v[j - 1] + 1, v[j], v[j + k], v[j + k + 1] - 1);
  177.         }
  178.     }
  179.  
  180.     long long countNumber(int mask) {
  181.         SegmentTree myit(n);
  182.         long long res = 0;
  183.         FOR(i, 1, n) {
  184.             FOR(j, 1, m) if (BIT(mask, j - 1)) {
  185.                 for (const Update &u : updates[j][i]) myit.update(u.fr, u.to, u.delta);
  186.             }
  187.             res += myit.getNumZero();
  188.         }
  189.  
  190.         return res - 1LL * n * (n - 1) / 2;
  191.     }
  192.  
  193.     void process(void) {
  194.         prepare();
  195.  
  196.         long long res = 1LL * n * (n + 1) / 2;
  197.         FOR(mask, 1, MASK(m) - 1) {
  198.             long long tmp = countNumber(mask);
  199.             if (__builtin_popcount(mask) % 2 == 0) res += tmp;
  200.             else res -= tmp;
  201.         }
  202.         cout << res << "\n";
  203.     }
  204. }
  205.  
  206. int main(void) {
  207.     init();
  208.     if (subtask1::check()) return subtask1::process(), 0;
  209.     if (subtask2::check()) return subtask2::process(), 0;
  210.     if (subtask4::check()) return subtask4::process(), 0;
  211.     return 0;
  212. }
  213.  
Success #stdin #stdout 0.01s 18916KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/77iphW
language:
C++14 (gcc 8.3)
created:
22 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!