fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. class SegmentTree
  8. {
  9. private:
  10.     vector<int> st, lazy, A;
  11.     int N;
  12.  
  13.     int lt(int p) { return p << 1; }
  14.     int rt(int p) { return (p << 1) + 1;}
  15.  
  16.     void build(int p, int L, int R) {
  17.         if(L == R)
  18.             st[p] = A[L];
  19.         else {
  20.             build( lt(p), L, (L+R)/2);
  21.             build( rt(p), (L+R)/2 + 1, R);
  22.             st[p] = st[lt(p)] + st[rt(p)];
  23.         }
  24.     }
  25.  
  26.     void set(int p, int L, int R, int i, int j) {
  27.         update(p, L, R);
  28.  
  29.         if( i >  R || j <  L ) return;
  30.         if( i <= L && R <= j ) {
  31.             st[p] = R - L + 1;
  32.  
  33.             if(L != R) lazy[ lt(p) ] = lazy[ rt(p) ] = 1;
  34.             return;
  35.         }
  36.  
  37.         set( lt(p), L, (L+R)/2, i, j  );
  38.         set( rt(p), (L+R)/2 + 1, R, i, j );
  39.         st[p] = st[ lt(p) ] + st[ rt(p) ];
  40.     }
  41.  
  42.     void clear(int p, int L, int R, int i, int j) {
  43.         update(p, L, R);
  44.  
  45.         if( i >  R || j <  L ) return;
  46.         if( i <= L && R <= j ) {
  47.             st[p] = 0;
  48.  
  49.             if(L != R) lazy[ lt(p) ] = lazy[ rt(p) ] = 0;
  50.             return;
  51.         }
  52.  
  53.         clear( lt(p), L, (L+R)/2, i, j  );
  54.         clear( rt(p), (L+R)/2 + 1, R, i, j );
  55.         st[p] = st[ lt(p) ] + st[ rt(p) ];
  56.     }
  57.  
  58.     void flip(int p, int L, int R, int i, int j) {
  59.         update(p, L, R);
  60.  
  61.         if( i >  R || j <  L ) return;
  62.         if( i <= L && R <= j ) {
  63.             st[p] = R - L + 1 - st[p];
  64.  
  65.             if(L != R) {
  66.                 lazy[ lt(p) ] = go_flip( lt(p) );
  67.                 lazy[ rt(p) ] = go_flip( rt(p) );
  68.             }
  69.             return;
  70.         }
  71.  
  72.         flip( lt(p), L, (L+R)/2, i, j  );
  73.         flip( rt(p), (L+R)/2 + 1, R, i, j );
  74.         st[p] = st[ lt(p) ] + st[ rt(p) ];
  75.     }
  76.  
  77.     int rsq(int p, int L, int R, int i, int j) {
  78.         if( i >  R || j <  L ) return 0;
  79.  
  80.         update(p, L, R);
  81.  
  82.         if( i <= L && R <= j ) return st[p];
  83.  
  84.         return rsq( lt(p), L, (L+R)/2, i, j)
  85.              + rsq( rt(p), (L+R)/2 + 1, R, i, j);
  86.     }
  87.  
  88.     int go_flip(int p) {
  89.         if( lazy[p] == 0 || lazy[p] == 1 ) return !lazy[p];
  90.         if( lazy[p] == 2 ) return -1;
  91.         return 2;
  92.     }
  93.  
  94.     void update(int p, int L, int R) {
  95.         if( lazy[p] < 0 ) return;
  96.         if( lazy[p] == 0 || lazy[p] == 1 ) {
  97.             st[p] = lazy[p] ? R - L + 1 : 0;
  98.  
  99.             if(L != R) lazy[lt(p)] = lazy[rt(p)] = lazy[p];
  100.         } else {
  101.             st[p] = R - L + 1 - st[p];
  102.  
  103.             if(L != R) {
  104.                 lazy[ lt(p) ] = go_flip( lt(p) );
  105.                 lazy[ rt(p) ] = go_flip( rt(p) );
  106.             }
  107.         }
  108.         lazy[p] = -1;
  109.     }
  110.  
  111. public:
  112.     SegmentTree(const vector<int> _A) {
  113.         A = _A; N = (int)_A.size();
  114.         st.assign(4 * N, 0);
  115.         lazy.assign(4 * N, -1);
  116.         build(1, 0, N - 1);
  117.     }
  118.  
  119.     void set  (int i, int j) { set  (1, 0, N - 1, i, j); }
  120.     void clear(int i, int j) { clear(1, 0, N - 1, i, j); }
  121.     void flip (int i, int j) { flip (1, 0, N - 1, i, j); }
  122.     int  rsq  (int i, int j) { rsq  (1, 0, N - 1, i, j); }
  123. };
  124.  
  125. vector<int> pirates;
  126.  
  127. int main()
  128. {
  129.     int T;
  130.  
  131.     scanf("%d\n", &T);
  132.  
  133.     for(int k = 1; k <= T; ++k) {
  134.         printf("Case %d:\n", k);
  135.  
  136.         int M; scanf("%d\n", &M);
  137.  
  138.         while(M--) {
  139.             int  t;         scanf("%d\n", &t);
  140.             char input[51]; scanf("%s\n", input);
  141.  
  142.             int N = strlen( input );
  143.  
  144.             while(t--)
  145.                 for(int i = 0; i < N; ++i)
  146.                     pirates.push_back( input[i] - '0' );
  147.         }
  148.  
  149.         SegmentTree pirates_count( pirates );
  150.  
  151.         int Q, count = 0;
  152.         scanf("%d\n", &Q);
  153.  
  154.         while(Q--) {
  155.             char op; int i, j;
  156.  
  157.             scanf("%c %d %d\n", &op, &i, &j);
  158.  
  159.             if(op == 'F')
  160.                 pirates_count.set(i, j);
  161.             else if(op == 'E')
  162.                 pirates_count.clear(i, j);
  163.             else if(op == 'I')
  164.                 pirates_count.flip(i, j);
  165.             else
  166.                 printf("Q%d: %d\n", ++count, pirates_count.rsq(i, j));
  167.         }
  168.  
  169.         pirates.clear();
  170.     }
  171. }
  172.  
Runtime error #stdin #stdout #stderr 1.92s 528896KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case 1:
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/KuwNo1
language:
C++14 (gcc 8.3)
created:
8 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!