fork download
copy 
  1. #include<bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #define int long long
  4. #define maxn 400005
  5. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6.  
  7. using namespace std;
  8.  
  9. int N;
  10. long long L, R;
  11.  
  12. long long a[maxn], pref[maxn];
  13. long long D[maxn];
  14. long long comp[maxn];
  15. int pos[maxn];
  16.  
  17. int nComp;
  18. int st[4 * maxn];
  19.  
  20. void update(int id, int l, int r, int pos, int val){
  21.     if(l == r){
  22.         st[id] += val;
  23.         return;
  24.     }
  25.     int mid = (l + r) >> 1;
  26.     if(pos <= mid) update(id << 1, l, mid, pos, val);
  27.     else update(id << 1 | 1, mid + 1, r, pos, val);
  28.     st[id] = st[id << 1] + st[id << 1 | 1];
  29. }
  30.  
  31. int get(int id, int l, int r, int u, int v){
  32.     if(v < l || r < u) return 0;
  33.     if(u <= l && r <= v) return st[id];
  34.     int mid = (l + r) >> 1;
  35.     return get(id << 1, l, mid, u, v)
  36.          + get(id << 1 | 1, mid + 1, r, u, v);
  37. }
  38.  
  39. int32_t main(){
  40.     itachi;
  41.  
  42.     cin >> N >> L >> R;
  43.     for(int i = 1; i <= N; i++){
  44.         cin >> a[i];
  45.         pref[i] = pref[i-1] + a[i];
  46.     }
  47.  
  48.     // Build D
  49.     D[0] = 0;
  50.     for(int i = 1; i <= N; i++) D[i] = pref[i];
  51.     for(int i = 1; i <= N-1; i++) D[N+i] = pref[N] + pref[i];
  52.  
  53.     int M = 2 * N;
  54.  
  55.     // compress
  56.     for(int i = 0; i < M; i++) comp[i] = D[i];
  57.     sort(comp, comp + M);
  58.     nComp = unique(comp, comp + M) - comp;
  59.  
  60.     for(int i = 0; i < M; i++){
  61.         pos[i] = lower_bound(comp, comp + nComp, D[i]) - comp;
  62.     }
  63.  
  64.     auto getRange = [&](long long x, long long y){
  65.         if(x > y) return 0LL;
  66.         int l = lower_bound(comp, comp + nComp, x) - comp;
  67.         int r = upper_bound(comp, comp + nComp, y) - comp - 1;
  68.         if(l > r) return 0LL;
  69.         return (long long)get(1, 0, nComp-1, l, r);
  70.     };
  71.  
  72.     // ================= total =================
  73.     long long total = 0;
  74.  
  75.     for(int r = 1; r <= 2*N-2; r++){
  76.         int addIdx = r - 1;
  77.         if(addIdx < N) update(1, 0, nComp-1, pos[addIdx], 1);
  78.  
  79.         int remIdx = r - N;
  80.         if(remIdx >= 0) update(1, 0, nComp-1, pos[remIdx], -1);
  81.  
  82.         total += getRange(D[r] - R, D[r] - L);
  83.     }
  84.  
  85.     // clear tree
  86.     memset(st, 0, sizeof(st));
  87.  
  88.     // ================= bad[i] =================
  89.     long long bad[maxn] = {0};
  90.     long long cur = 0;
  91.  
  92.     // i = 0 window: D[1..N]
  93.     for(int j = 1; j <= N; j++){
  94.         cur += getRange(D[j] - R, D[j] - L);
  95.         update(1, 0, nComp-1, pos[j], 1);
  96.     }
  97.     bad[0] = cur;
  98.  
  99.     for(int i = 1; i < N; i++){
  100.         long long x = D[i];
  101.  
  102.         update(1, 0, nComp-1, pos[i], -1);
  103.         cur -= getRange(x + L, x + R);
  104.  
  105.         long long y = D[i + N];
  106.         cur += getRange(y - R, y - L);
  107.         update(1, 0, nComp-1, pos[i + N], 1);
  108.  
  109.         bad[i] = cur;
  110.     }
  111.  
  112.     for(int i = 0; i < N; i++){
  113.         cout << total - bad[i] << ' ';
  114.     }
  115.  
  116.     return 0;
  117. }
Success #stdin #stdout 0.01s 23184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/268SCk
language:
C++14 (gcc 8.3)
created:
2 hours 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!