fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. const int N=1e5+5;
  6. const int M=3e5;
  7.  
  8.  
  9.  
  10.  
  11. int n,x,t[4*N],ob[4*N];
  12. string s;
  13.  
  14. inline void push(int v,int l,int r){
  15.     if(ob[v]!=-1){
  16.         ob[v+v]=ob[v+v+1]=ob[v];
  17.         int mid=(r+l)>>1;
  18.         t[v+v]=(mid-l+1)*ob[v];
  19.         t[v+v+1]=(r-mid)*ob[v];
  20.         ob[v]=-1;
  21.     }
  22. }
  23.  
  24. void update(int v,int l,int r,int tl,int tr,int val){
  25.     if(l>r || l>tr || tl>r || tl>tr){
  26.         return;
  27.     }
  28.     if(tl<=l && r<=tr){
  29.         t[v]=(r-l+1)*val;
  30.         ob[v]=val;
  31.         return;
  32.     }
  33.     push(v,l,r);
  34.     int mid=(r+l)>>1;
  35.     update(v+v,l,mid,tl,tr,val);
  36.     update(v+v+1,mid+1,r,tl,tr,val);
  37.     t[v]=t[v+v]+t[v+v+1];
  38. }
  39.  
  40. int first_zero(int v,int l,int r,int tl,int tr){
  41.     /// if our interval full (so there's no zeros)
  42.     if(t[v]==r-l+1){
  43.         return -1;
  44.     }
  45.     if(l>r || l>tr || tl>r || tl>tr){
  46.         return -1;
  47.     }
  48.     if(l==r){
  49.         return l;
  50.     }
  51.     push(v,l,r);
  52.     int mid=(r+l)>>1;
  53.     /// we should find first position
  54.     int val=first_zero(v+v,l,mid,tl,tr);
  55.     if(val==-1){
  56.         return first_zero(v+v+1,mid+1,r,tl,tr);
  57.     }
  58.     else{
  59.         return val;
  60.     }
  61. }
  62.  
  63. int first_one(int v,int l,int r,int tl,int tr){
  64.     /// if our interval empty (so there's no ones)
  65.     if(t[v]==0){
  66.         return -1;
  67.     }
  68.     if(l>r || l>tr || tl>r || tl>tr){
  69.         return -1;
  70.     }
  71.     if(l==r){
  72.         return l;
  73.     }
  74.     push(v,l,r);
  75.     int mid=(r+l)>>1;
  76.     /// we should find first position
  77.     int val=first_one(v+v,l,mid,tl,tr);
  78.     if(val==-1){
  79.         return first_one(v+v+1,mid+1,r,tl,tr);
  80.     }
  81.     else{
  82.         return val;
  83.     }
  84. }
  85.  
  86. int main(){
  87.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  88.     memset(ob,-1,sizeof(ob));
  89.     cin>>n;
  90.     for(int i=1;i<=n;i++){
  91.         cin>>s>>x;
  92.         if(s=="add"){
  93.             /// find first zero on interval x..M
  94.  
  95.             int U=first_zero(1,0,M,x,M);
  96.  
  97.             /// assing 0 on interval x..U-1
  98.  
  99.             update(1,0,M,x,U-1,0);
  100.  
  101.             /// assing 1 in position U
  102.  
  103.             update(1,0,M,U,U,1);
  104.         }
  105.         else{
  106.             /// find first one on interval x..M
  107.  
  108.             int U=first_one(1,0,M,x,M);
  109.  
  110.             /// assing 1 on interval x..U-1
  111.  
  112.             update(1,0,M,x,U-1,1);
  113.  
  114.             /// assing 0 in position U
  115.  
  116.             update(1,0,M,U,U,0);
  117.         }
  118.         /// sum on interval 0..M
  119.  
  120.         cout<<t[1]<<"\n";
  121.     }
  122. }
  123.  
Success #stdin #stdout 0s 19176KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gHXEt3
language:
C++14 (gcc 8.3)
created:
6 years 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!