fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. const ll N=1e6+7;
  6. ll seg[N*4],lazy[N*4],on[N*4],cnt[N*4];
  7. ll state[N],point[N],nw[N];
  8.  
  9. void build(ll n,ll b,ll e){
  10.     if(b==e){
  11.         if(nw[b]==1) on[n]=1;
  12.         return;
  13.     }
  14.     ll mid=(b+e)/2;
  15.     build(2*n,b,mid);
  16.     build(2*n+1,mid+1,e);
  17.     on[n]=on[2*n]+on[2*n+1];
  18. }
  19. void update(ll n,ll b,ll e,ll l,ll r){    
  20.    	if(cnt[n]%2) on[n]=e-b+1-on[n];
  21. 	if(b!=e) {
  22. 		cnt[2*n]+=cnt[n];
  23. 		cnt[2*n+1]+=cnt[n];
  24. 	}
  25. 	cnt[n]=0;
  26.     if(e<l || b>r) return;
  27.     if(b>=l && e<=r){
  28.     	cnt[n]++;
  29.     	if(b!=e){cnt[2*n]++;cnt[2*n+1]++;}
  30.         if(cnt[n]%2) on[n]=e-b+1-on[n];
  31.         cnt[n]=0;
  32.         return ;                	       
  33.     }
  34.     ll mid=(b+e)/2;
  35.     update(2*n,b,mid,l,r);
  36.     update(2*n+1,mid+1,e,l,r);
  37.     on[n]=on[2*n]+on[2*n+1];
  38. }
  39.  
  40. int main(){
  41.     ios_base::sync_with_stdio(0);
  42.     cin.tie(0);
  43.     ll n,m;cin>>n>>m;
  44.     ll ans=0;
  45.     ll neg[n+1]={0},id=1;
  46.     for(ll i=1;i<=n;i++){
  47.         cin>>state[i]>>point[i];
  48.         ans+=point[i];
  49.         if (state[i]!=-1){
  50.         	nw[id]=state[i];
  51.         	id++;
  52.     	}
  53.     	neg[i]=neg[i-1]+(state[i]==-1);
  54.     }
  55.     n=id-1;
  56.     build(1,1,n); 
  57.     for(ll i=0;i<m;i++){
  58.         char ch;
  59.         cin>>ch;
  60.         if(ch=='C'){
  61.             ll val;cin>>val;
  62.             ans+=on[1]*val;
  63.         }
  64.         else{ 
  65.             ll l,r;cin>>l>>r;
  66.             l++;r++;
  67.             l-=neg[l-1];r-=neg[r];
  68.             if(l>r) continue;
  69.             update(1,1,n,l,r);
  70.         }
  71.     }
  72.     cout<<ans<<"\n";
  73. }
Success #stdin #stdout 0.01s 9724KB
comments (?)
stdin
copy 
7 5
0 4
1 -4
-1 2
1 4
0 2
0 0 
-1 2
C 2
W 0 4
W 2 5
W 0 2
C 3
stdout
copy 
23
https://ideone.com/dt2Lx7
language:
C++14 (gcc 8.3)
created:
15 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!