fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1234567;
  6.  
  7. char a[N];
  8. int sum[10 * N];
  9. int flag[10 * N];
  10. char ss[55];
  11.  
  12. const int data[] = {3, 2, 1, 0};
  13.  
  14. inline int inv(int x) {
  15.   return data[x];
  16. }
  17.  
  18. void build(int x, int l, int r) {
  19.   flag[x] = 0;
  20.   if (l == r) {
  21.     sum[x] = a[l] - '0';
  22.   } else {  
  23.     int mid = (l + r) / 2;
  24.     build(x + x, l, mid);
  25.     build(x + x + 1, mid + 1, r);
  26.     sum[x] = sum[x + x] + sum[x + x + 1];
  27.   }
  28. }
  29.  
  30. void push(int x, int l, int r) {
  31.   if (flag[x] == 1) {
  32.     sum[x] = 0;
  33.     flag[x + x] = flag[x + x + 1] = 1;
  34.     flag[x] = 0;
  35.     return;
  36.   }
  37.   if (flag[x] == 2) {
  38.     sum[x] = r - l + 1;
  39.     flag[x + x] = flag[x + x + 1] = 2;
  40.     flag[x] = 0;
  41.     return;
  42.   }
  43.   if (flag[x] == 3) {
  44.     sum[x] = r - l + 1 - sum[x];
  45.     flag[x + x] = inv(flag[x + x]);
  46.     flag[x + x + 1] = inv(flag[x + x + 1]);
  47.     flag[x] = 0;
  48.     return;
  49.   }
  50. }
  51.  
  52. void assign(int x, int l, int r, int ll, int rr, int v) {
  53.   int mid = (l + r) / 2;
  54.   push(x, l, r);
  55.   push(x + x, l, mid);
  56.   push(x + x + 1, mid + 1, r);
  57.   if (l == ll && r == rr) {
  58.     sum[x] = v * (r - l + 1);
  59.     flag[x + x] = flag[x + x + 1] = v + 1; 
  60.   } else {
  61.     int mid = (l + r) / 2;
  62.     if (rr <= mid) {
  63.       assign(x + x, l, mid, ll, rr, v);
  64.     } else if (ll > mid) {
  65.       assign(x + x + 1, mid + 1, r, ll, rr, v);
  66.     } else {
  67.       assign(x + x, l, mid, ll, mid, v);
  68.       assign(x + x + 1, mid + 1, r, mid + 1, rr, v);
  69.     }
  70.     sum[x] = sum[x + x] + sum[x + x + 1];
  71.   }
  72. }
  73.  
  74. void inverse(int x, int l, int r, int ll, int rr) {
  75.   int mid = (l + r) / 2;
  76.   push(x, l, r);
  77.   push(x + x, l, mid);
  78.   push(x + x + 1, mid + 1, r);
  79.   if (l == ll && r == rr) {
  80.     sum[x] = r - l + 1 - sum[x];
  81.     flag[x + x] = inv(flag[x + x]);
  82.     flag[x + x + 1] = inv(flag[x + x + 1]);
  83.   } else {
  84.     int mid = (l + r) / 2;
  85.     if (rr <= mid) {
  86.       inverse(x + x, l, mid, ll, rr);
  87.     } else if (ll > mid) {
  88.       inverse(x + x + 1, mid + 1, r, ll, rr);
  89.     } else {
  90.       inverse(x + x, l, mid, ll, mid);
  91.       inverse(x + x + 1, mid + 1, r, mid + 1, rr);
  92.     }
  93.     sum[x] = sum[x + x] + sum[x + x + 1];
  94.   }
  95. }
  96.  
  97. int query(int x, int l, int r, int ll, int rr) {
  98.   int mid = (l + r) / 2;
  99.   push(x, l, r);
  100.   push(x + x, l, mid);
  101.   push(x + x + 1, mid + 1, r);
  102.   if (l == ll && r == rr) {
  103.     return sum[x];
  104.   } else {
  105.     int mid = (l + r) / 2;
  106.     if (rr <= mid) {
  107.       return query(x + x, l, mid, ll, rr); 
  108.     }
  109.     if (ll > mid) {
  110.       return query(x + x + 1, mid + 1, r, ll, rr);
  111.     }
  112.     return query(x + x, l, mid, ll, mid) + query(x + x + 1, mid + 1, r, mid + 1, rr);
  113.   }
  114. }
  115.  
  116. int main() {  
  117.   //freopen("input.txt", "r", stdin);
  118.   //freopen("output.txt", "w", stdout);
  119.   int tests;
  120.   scanf("%d", &tests);
  121.   int tcase = 0;
  122.   while (tests--) {
  123.     tcase++;
  124.     printf("Case %d:\n", tcase);
  125.     int m;
  126.     scanf("%d", &m);
  127.     int s = 0;
  128.     while (m--) {
  129.       int t;
  130.       scanf("%d%s", &t, ss + 1);
  131.       int n = strlen(ss + 1);
  132.       for (int i = 0; i < t; i++) {
  133.         for (int j = s + 1; j <= s + n; j++) {
  134.           a[j] = ss[j - s];
  135.         }
  136.         s += n;
  137.       }
  138.     }
  139.     build(1, 1, s);
  140.     int q;
  141.     scanf("%d", &q);
  142.     int qry = 0;
  143.     while (q--) {
  144.       char ch;
  145.       int x, y;
  146.       scanf(" %c%d%d", &ch, &x, &y);
  147.       x++; y++;
  148.       if (ch == 'F') {
  149.         assign(1, 1, s, x, y, 1);
  150.       } 
  151.       if (ch == 'E') {
  152.         assign(1, 1, s, x, y, 0);
  153.       }
  154.       if (ch == 'I') {
  155.         inverse(1, 1, s, x, y);
  156.       }
  157.       if (ch == 'S') {
  158.         qry++;
  159.         printf("Q%d: %d\n", qry, query(1, 1, s, x, y));
  160.       }
  161.     }
  162.   }
  163.   return 0;
  164. }
Time limit exceeded #stdin #stdout 5s 101056KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ICQv6M
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!