fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. #define int long long
  6.  
  7. // Code for Mo's Algorithm based on CP-algorithms
  8.  
  9. const int block_size = 325;
  10. const int MAXN = 100005;
  11.  
  12. int n;
  13. int count[block_size];
  14. int sum[block_size];
  15. int num[MAXN];
  16. int ct[MAXN];
  17. int st[MAXN];
  18. int a[MAXN];
  19.  
  20. void upd(int x, int v) {
  21.   if(x == 0)
  22.     return;
  23.  
  24.   ct[x] += v;
  25.   st[x] += v*(x-1);
  26.   count[x/block_size] += v;
  27.   sum[x/block_size] += v*(x-1);
  28. }
  29.  
  30. void remove(int idx) {
  31.   upd(num[a[idx]], -1);
  32.   num[a[idx]]--;
  33.   upd(num[a[idx]], +1);
  34. }
  35.  
  36. void add(int idx) {
  37.   upd(num[a[idx]], -1);
  38.   num[a[idx]]++;
  39.   upd(num[a[idx]], +1);
  40. }
  41.  
  42. int get_answer(int k) {
  43.   int j = 0;
  44.   int done = 0;
  45.  
  46.   while(j < block_size && sum[j] <= k) {
  47.     k -= sum[j];
  48.     done += count[j];
  49.     j++;
  50.   }
  51.  
  52.   if(j == block_size)
  53.     return done;
  54.  
  55.   int id = j*block_size;
  56.   while(st[id] <= k) {
  57.     k -= st[id];
  58.     done += ct[id];
  59.     id++;
  60.   }
  61.  
  62.   int add = k/(id-1);
  63.   return done + add;
  64. }
  65.  
  66. struct Query {
  67.   int l, r, idx, k;
  68.   bool operator<(Query other) const
  69.   {
  70.     return std::make_pair(l / block_size, r) <
  71.       std::make_pair(other.l / block_size, other.r);
  72.   }
  73. };
  74.  
  75. std::vector<int> mo_s_algorithm(std::vector<Query> queries) {
  76.   std::vector<int> answers(queries.size());
  77.   std::sort(queries.begin(), queries.end());
  78.  
  79.   int cur_l = 0;
  80.   int cur_r = -1;
  81.  
  82.   for (Query q : queries) {
  83.     while (cur_l > q.l) {
  84.       cur_l--;
  85.       add(cur_l);
  86.     }
  87.     while (cur_r < q.r) {
  88.       cur_r++;
  89.       add(cur_r);
  90.     }
  91.     while (cur_l < q.l) {
  92.       remove(cur_l);
  93.       cur_l++;
  94.     }
  95.     while (cur_r > q.r) {
  96.       remove(cur_r);
  97.       cur_r--;
  98.     }
  99.     answers[q.idx] = get_answer(q.k);
  100.   }
  101.   return answers;
  102. }
  103.  
  104. signed main() {
  105.   std::ios::sync_with_stdio(false);
  106.   std::cin.tie(0);
  107.  
  108.   std::cin >> n;
  109.  
  110.   for(int i = 0; i < n; i++)
  111.     std::cin >> a[i];
  112.  
  113.   std::vector<Query> qs;
  114.   int q;
  115.   std::cin >> q;
  116.  
  117.   for(int i = 0; i < q; i++) {
  118.     int l, r, k;
  119.     std::cin >> l >> r >> k;
  120.     l--; r--;
  121.     qs.push_back({l, r, i, k});
  122.   }
  123.  
  124.   std::vector<int> ans = mo_s_algorithm(qs);
  125.  
  126.   for(int j : ans)
  127.     std::cout << j << std::endl;
  128.  
  129.   return 0;
  130. }
Runtime error #stdin #stdout 2.07s 2095868KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oFkQOM
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!