fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int n,m;
  6.  
  7. struct tree
  8. {
  9.     int flag,sum;
  10. };
  11. tree seg[500000];
  12. int lazy[500000]={0};
  13.  
  14. void build_tree(int pos,int low,int high)
  15. {
  16.     if(low==high)
  17.     {
  18.         seg[pos].flag=seg[pos].sum=0;
  19.         return;
  20.     }
  21.     int mid=(low+high)/2;
  22.     build_tree(2*pos+1,low,mid);
  23.     build_tree(2*pos+2,mid+1,high);
  24. }
  25. void update(int pos,int low,int high,int l,int r)
  26. {
  27.  
  28.     if(lazy[pos]==-1)
  29.     {
  30.         seg[pos].flag^=1;
  31.         seg[pos].sum=(high-low+1)*(seg[pos].flag);
  32.         if(low!=high)
  33.         {
  34.             lazy[2*pos+1]=-1;
  35.             lazy[2*pos+2]=-1;
  36.         }
  37.         lazy[pos]=0;
  38.     }
  39.  
  40.  
  41.     if(low>r||high<l)
  42.         return;
  43.  
  44.     if(low>=l&&high<=r)
  45.     {
  46.         seg[pos].flag^=1;
  47.         seg[pos].sum=(high-low+1)*(seg[pos].flag);
  48.         if(low!=high)
  49.         {
  50.             lazy[2*pos+1]=-1;
  51.             lazy[2*pos+2]=-1;
  52.         }
  53.         return;
  54.     }
  55.  
  56.     int mid=(low+high)/2;
  57.     update(2*pos+1,low,mid,l,r);
  58.     update(2*pos+2,mid+1,high,l,r);
  59.     seg[pos].flag=seg[2*pos+1].flag||seg[2*pos+2].flag;
  60.     seg[pos].sum=seg[2*pos+1].sum+seg[2*pos+2].sum;
  61. }
  62.  
  63. int query(int pos,int low,int high,int l,int r)
  64. {
  65.     if(low>r||high<l)
  66.         return 0;
  67.     if(lazy[pos]==-1)
  68.     {
  69.         seg[pos].flag^=1;
  70.         seg[pos].sum=(high-low+1)*(seg[pos].flag);
  71.         if(low!=high)
  72.         {
  73.             lazy[2*pos+1]=-1;
  74.             lazy[2*pos+2]=-1;
  75.         }
  76.         lazy[pos]=0;
  77.     }
  78.     if(low>=l&&high<=r)
  79.         return(seg[pos].sum);
  80.  
  81.     int mid=(low+high)/2;
  82.     int p1=query(2*pos+1,low,mid,l,r);
  83.     int p2=query(2*pos+2,mid+1,high,l,r);
  84.     return (p1+p2);
  85. }
  86. int main()
  87. {
  88.  
  89.    cin>>n>>m;
  90.    int x,y,z;
  91.    build_tree(0,0,n-1);
  92.    while(m--)
  93.    {
  94.         cin>>x>>y>>z;
  95.         if(x==0)
  96.         {
  97.             update(0,0,n-1,y-1,z-1);
  98.         }
  99.         else
  100.         {
  101.             cout<<query(0,0,n-1,y-1,z-1)<<endl;
  102.         }
  103.    }
  104. }
  105.  
Time limit exceeded #stdin #stdout 5s 8294400KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2jfu1K
language:
C++ (gcc 8.3)
created:
7 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!