fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define all(ac) ac.begin(),ac.end()
  5. struct BIT {
  6.     int n;
  7.     vector <int> bit;
  8.     BIT(int n): n(n), bit(n+1,0) {}
  9.     void update(int x, int  val) {
  10.         for(;x<=n;x+=x&-x) bit[x]+=val;
  11.         return;
  12.     }
  13.     int get(int x) {
  14.         int res=0;
  15.         for(;x;x-=x&-x) res+=bit[x];
  16.         return res;
  17.     }
  18.     int get(int l, int r) {return get(r)-get(l-1);}
  19. };
  20. int32_t main() {
  21.     ios::sync_with_stdio(false);
  22.     cin.tie(0), cout.tie(0);
  23.     int n,m,k; cin >> n >> m >> k;
  24.     int a[n+1],sum=0;
  25.     for(int i=1;i<=n;i++) cin >> a[i],sum+=a[i];
  26.     int s[k+1];
  27.     for(int i=1;i<=k;i++) cin >> s[i];
  28.     int l[m+1],r[m+1],w[m+1];
  29.     for(int i=1;i<=m;i++) cin >> l[i] >> r[i] >> w[i];
  30.     vector <int> g[m+1];
  31.     int check[n+1];
  32.     memset(check,-1,sizeof check);
  33.     for(int x=1;x<=k;x++) {
  34.         int lo[n+1], hi[n+1];
  35.         for(int i=1;i<=n;i++) {
  36.             lo[i]=1, hi[i]=m;
  37.             if(a[i]==s[x]) check[i]=0;
  38.         }
  39.         while(true) {
  40.             int bye=1;
  41.             vector <pair<int,int> > vt;
  42.             for(int i=1;i<=n;i++) if(lo[i]<=hi[i] && check[i]) {
  43.                 int mid=(lo[i]+hi[i])>>1;
  44.                 vt.push_back({mid,i});
  45.                 bye=0;
  46.             }
  47.             if(bye) break;
  48.             BIT bit(n);
  49.             sort(all(vt));
  50.             int pos=1;
  51.             for(auto e:vt) {
  52.                 int mid=e.first, id=e.second;
  53.                 while(pos<=mid) bit.update(l[pos],w[pos]), bit.update(r[pos]+1,-w[pos]), pos++;
  54.                 int val=bit.get(id)+a[id];
  55.                 if(val>=s[x]) {
  56.                     hi[id]=mid-1;
  57.                     if(s[x]==val && (check[id]==-1 || check[id]>mid)) check[id]=mid;
  58.                 }
  59.                 else lo[id]=mid+1;
  60.             }
  61.         }
  62.     }
  63.     for(int i=1;i<=n;i++) if(check[i]>-1) g[check[i]].push_back(i);
  64.     BIT bit(n);
  65.     for(auto pos:g[0]) bit.update(pos,1);
  66.     for(int i=1;i<=m;i++) {
  67.         int cnt=r[i]-l[i]+1-bit.get(l[i],r[i]);
  68.         sum+=cnt*w[i];
  69.         for(auto pos:g[i]) bit.update(pos,1);
  70.         cout << sum << '\n';
  71.     }
  72.     return 0;
  73. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
5 2 2
5 3 2 4 1
3 4
1 4 1
1 5 3
stdout
copy 
17
23
https://ideone.com/l878ZX
language:
C++ (gcc 8.3)
created:
8 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!