fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct SparseMin {
  5.     int n; vector<int> lg; vector<vector<int>> st;
  6.     void build(const vector<int>& a){ // a is 1-indexed, size n+1
  7.         n = (int)a.size() - 1;
  8.         lg.assign(n+1,0);
  9.         for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
  10.         st.assign(lg[n]+1, vector<int>(n+1));
  11.         for(int i=1;i<=n;i++) st[0][i]=a[i];
  12.         for(int k=1;k<=lg[n];k++){
  13.             int len=1<<(k-1);
  14.             for(int i=1;i+(1<<k)-1<=n;i++)
  15.                 st[k][i]=min(st[k-1][i], st[k-1][i+len]);
  16.         }
  17.     }
  18.     inline int query(int l,int r) const{ // inclusive
  19.         if(l>r) return INT_MAX;
  20.         int k=lg[r-l+1];
  21.         return min(st[k][l], st[k][r-(1<<k)+1]);
  22.     }
  23. };
  24.  
  25. int main(){
  26.     ios::sync_with_stdio(false);
  27.     cin.tie(nullptr);
  28.     int n; if(!(cin>>n)) return 0;
  29.     vector<int>a(n+1);
  30.     for(int i=1;i<=n;i++) cin>>a[i];
  31.     int q; cin>>q;
  32.     vector<pair<int,int>> Q(q);
  33.     for(int i=0;i<q;i++) cin>>Q[i].first>>Q[i].second;
  34.  
  35.     const int A=100;
  36.     // positions by value
  37.     vector<vector<int>> pos(A+1);
  38.     for(int i=1;i<=n;i++) pos[a[i]].push_back(i);
  39.  
  40.     vector<long long> ans(q,0);
  41.  
  42.     // arrays reused per k
  43.     vector<int> Sk(n+1), Ck(n+1), Uk(n+1);
  44.  
  45.     for(int k=1;k<=A;k++){
  46.         // prefix counts of value k
  47.         Ck[0]=0;
  48.         for(int i=1;i<=n;i++) Ck[i]=Ck[i-1]+(a[i]==k);
  49.         // S_k: (<k => +a, >=k => -a)
  50.         Sk[0]=0;
  51.         for(int i=1;i<=n;i++) Sk[i]=Sk[i-1] + (a[i]<k ? a[i] : -a[i]);
  52.         // U_k = S_k + 2k * Ck
  53.         for(int i=0;i<=n;i++) Uk[i]=Sk[i] + 2*k*Ck[i];
  54.  
  55.         SparseMin RMQ_S, RMQ_U;
  56.         RMQ_S.build(Sk);
  57.         RMQ_U.build(Uk);
  58.  
  59.         const auto& P = pos[k];
  60.  
  61.         for(int id=0; id<q; id++){
  62.             int L=Q[id].first, R=Q[id].second;
  63.             int tot = Ck[R]-Ck[L-1];
  64.             if(tot==0) continue;
  65.  
  66.             int base = int(lower_bound(P.begin(), P.end(), L) - P.begin()); // first k in [L..]
  67.             // check if the block really fits inside [L,R]
  68.             // (by constraints of tot it must)
  69.  
  70.             auto ok = [&](int m)->bool{
  71.                 // pos_m: position of m-th k inside [L,R]; pos_0 = L-1
  72.                 int pos_m = (m==0 ? L-1 : P[base + m - 1]);
  73.                 // v1: for t in [L .. pos_m], x(t) = (Uk[t] - const0) must be >= 0
  74.                 int v1 = INT_MAX;
  75.                 if(pos_m >= L){
  76.                     int minU = RMQ_U.query(L, pos_m);
  77.                     int const0 = Sk[L-1] + 2*k*Ck[L-1];
  78.                     v1 = minU - const0;
  79.                 }
  80.                 // v2: for t in [pos_m+1 .. R], x(t) = (Sk[t]-Sk[L-1]) + 2k*m >= 0
  81.                 int left2 = max(L, pos_m+1);
  82.                 int minS = RMQ_S.query(left2, R);
  83.                 int v2 = (minS==INT_MAX ? INT_MAX : (minS - Sk[L-1] + 2*k*m));
  84.                 return min(v1, v2) >= 0;
  85.             };
  86.  
  87.             // binary search minimal rescued m in [0..tot]
  88.             int lo=0, hi=tot, res=tot;
  89.             while(lo<=hi){
  90.                 int mid=(lo+hi)>>1;
  91.                 if(ok(mid)){ res=mid; hi=mid-1; }
  92.                 else lo=mid+1;
  93.             }
  94.             ans[id] += (tot - res); // rescued are additions; gifts are the rest
  95.         }
  96.     }
  97.  
  98.     for(int i=0;i<q;i++) cout<<ans[i]<<"\n";
  99.     return 0;
  100. }
  101.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
6
4 3 8 3 9 2
3
1 3
2 4
1 6
stdout
copy 
0
0
1
https://ideone.com/5tBsNg
language:
C++14 (gcc 8.3)
created:
12 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!