fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAX_N = 100005;
  6. const int MAX_Q = 100005;
  7. const int BLOCK = 855;
  8.  
  9. struct Query {
  10.     int l, u, v, k, id;
  11.     friend bool operator<(Query &A, Query &B) {
  12.         if (A.u / BLOCK != B.u / BLOCK) {
  13.             return A.u / BLOCK < B.u / BLOCK;
  14.         }
  15.         return A.v < B.v;
  16.     }
  17. };
  18.  
  19. int n, numQuery;
  20. int a[MAX_N];
  21. Query queries[MAX_Q];
  22. vector<pair<int, int> > compress;
  23. int valueAt[MAX_N + 2 * MAX_Q];
  24. long long sum[MAX_N], sum_in_bl[MAX_N / BLOCK + 2];
  25. int answer[MAX_Q];
  26.  
  27. void add(int pos, int val) {
  28.     if (valueAt[pos] == 0) {
  29.         return;
  30.     }
  31.     int x = valueAt[pos];
  32.     sum[x] += val * a[x];
  33.     sum_in_bl[x / BLOCK] += val * a[x];
  34. }
  35.  
  36. int get(int pos, int k) {
  37.     for (int i = pos; i <= min(n, (pos / BLOCK + 1) * BLOCK - 1); i++) {
  38.         if (sum[i] > k) {
  39.             return i - pos;
  40.         } else {
  41.             k -= sum[i];
  42.         }
  43.     }
  44.  
  45.     for (int i = pos / BLOCK + 1; i <= n / BLOCK; i++) {
  46.         if (sum_in_bl[i] > k) {
  47.             for (int j = max(0, i * BLOCK); j <= min(n, (i + 1) * BLOCK - 1); j++) {
  48.                 if (sum[j] > k) {
  49.                     return j - pos;
  50.                 } else {
  51.                     k -= sum[j];
  52.                 }
  53.             }
  54.             break;
  55.         } else {
  56.             k -= sum_in_bl[i];
  57.         }
  58.     }
  59.  
  60.     return n - pos + 1;
  61. }
  62.  
  63. int main() {
  64.     ios::sync_with_stdio(0);
  65.     cin.tie(0);
  66.     cout.tie(0);
  67.  
  68.     freopen("SHOPPING.inp", "r", stdin);
  69.     freopen("SHOPPING.out", "w", stdout);
  70.  
  71.     cin >> n >> numQuery;
  72.  
  73.     for (int i = 1; i <= n; i++) {
  74.         cin >> a[i];
  75.         compress.emplace_back(a[i], -i);
  76.     }
  77.  
  78.     for (int i = 1; i <= numQuery; i++) {
  79.         cin >> queries[i].l >> queries[i].u >> queries[i].v >> queries[i].k;
  80.         queries[i].id = i;
  81.         compress.emplace_back(queries[i].u, i);
  82.         compress.emplace_back(queries[i].v, i + numQuery);
  83.     }
  84.  
  85.     sort(compress.begin(), compress.end(), [&](pair<int, int> &x, pair<int, int> &y) {
  86.         if (x.first != y.first) {
  87.             return x.first < y.first;
  88.         }
  89.  
  90.         if (x.second < 0) {
  91.             return (y.second > numQuery);
  92.         }
  93.  
  94.         if (x.second <= numQuery) {
  95.             if (y.second < 0) {
  96.                 return true;
  97.             }
  98.             return x.second < y.second;
  99.         }
  100.  
  101.         return false;
  102.     });
  103.  
  104.     for (int i = 0; i < (int)compress.size(); i++) {
  105.         pair<int, int> x = compress[i];
  106.         if (x.second < 0) {
  107.             valueAt[i + 1] = -x.second;
  108.         } else {
  109.             if (x.second > numQuery) {
  110.                 queries[x.second - numQuery].v = i + 1;
  111.             } else {
  112.                 queries[x.second].u = i + 1;
  113.             }
  114.         }
  115.     }
  116.  
  117.     sort(queries + 1, queries + numQuery + 1);
  118.  
  119.     int curLeft = queries[1].u, curRight = queries[1].u - 1;
  120.  
  121.     for (int i = 1; i <= numQuery; i++) {
  122.         while (curRight < queries[i].v) {
  123.             add(++curRight, +1);
  124.         }
  125.         while (curRight > queries[i].v) {
  126.             add(curRight--, -1);
  127.         }
  128.         while (curLeft < queries[i].u) {
  129.             add(curLeft++, -1);
  130.         }
  131.         while (curLeft > queries[i].u) {
  132.             add(--curLeft, +1);
  133.         }
  134.         answer[queries[i].id] = get(queries[i].l, queries[i].k);
  135.     }
  136.  
  137.     for (int i = 1; i <= numQuery; i++) {
  138.         cout << answer[i] << '\n';
  139.     }
  140.  
  141.     return 0;
  142. }
  143.  
Success #stdin #stdout 0s 5960KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3Dw70r
language:
C++14 (gcc 8.3)
created:
3 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!