daily pastebin goal
46%
SHARE
TWEET

Untitled

a guest Apr 16th, 2018 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ok cerr << "ok" << endl;
  6.  
  7. string s;
  8.  
  9. const int N = (int)160000;
  10. const int blocksz = 400;
  11.  
  12. struct block {
  13.     int a[blocksz];
  14.     int aa;
  15.     bool allone, allzero;
  16.     block() {
  17.         memset(a, 0, sizeof a);
  18.         aa = 0;
  19.         allone = allzero = 0;
  20.     }
  21. };
  22. block bt[blocksz];
  23. int ans;
  24.  
  25. void upd(int pos) {
  26.     int idl = pos / blocksz;
  27.     if (bt[idl].allzero) {
  28.         bt[idl].allzero = 0;
  29.         memset(bt[idl].a, 0, sizeof bt[idl].a);
  30.     } else if (bt[idl].allone) {
  31.         bt[idl].allone = 0;
  32.         for (int i = 0; i < blocksz; i++) {
  33.             bt[idl].a[i] = 1;
  34.         }
  35.     }
  36.     for (int i = pos % blocksz; i < blocksz; i++) {
  37.         if (bt[idl].a[i] == 0) {
  38.             bt[idl].a[i] = 1;
  39.             bt[idl].aa++;
  40.             ans++;
  41.             return ;
  42.         } else {
  43.             bt[idl].aa--;
  44.             ans--;
  45.             bt[idl].a[i] = 0;
  46.         }
  47.     }
  48.     idl++;
  49.     while (bt[idl].aa == blocksz) {
  50.         bt[idl].allzero = 1;
  51.         bt[idl].allone = 0;
  52.         bt[idl].aa = 0;
  53.         ans -= blocksz;
  54.         idl++;
  55.     }
  56.     if (bt[idl].allzero) {
  57.         bt[idl].allzero = 0;
  58.         memset(bt[idl].a, 0, sizeof bt[idl].a);
  59.     } else if (bt[idl].allone) {
  60.         bt[idl].allone = 0;
  61.         for (int i = 0; i < blocksz; i++) {
  62.             bt[idl].a[i] = 1;
  63.         }
  64.     }
  65.     for (int i = 0; i < blocksz; i++) {
  66.         if (bt[idl].a[i] == 0) {
  67.             bt[idl].a[i] = 1;
  68.             bt[idl].aa++;
  69.             ans++;
  70.             return ;
  71.         } else {
  72.             bt[idl].aa--;
  73.             ans--;
  74.             bt[idl].a[i] = 0;
  75.         }
  76.     }
  77. }
  78.  
  79. void upd1(int pos) {
  80.     int idl = pos / blocksz;
  81.     if (bt[idl].allzero) {
  82.         bt[idl].allzero = 0;
  83.         memset(bt[idl].a, 0, sizeof bt[idl].a);
  84.     } else if (bt[idl].allone) {
  85.         bt[idl].allone = 0;
  86.         for (int i = 0; i < blocksz; i++) {
  87.             bt[idl].a[i] = 1;
  88.         }
  89.     }
  90.     for (int i = pos % blocksz; i < blocksz; i++) {
  91.         if (bt[idl].a[i] == 1) {
  92.             bt[idl].a[i] = 0;
  93.             bt[idl].aa--;
  94.             ans--;
  95.             return ;
  96.         } else {
  97.             bt[idl].aa++;
  98.             ans++;
  99.             bt[idl].a[i] = 1;
  100.         }
  101.     }
  102.     idl++;
  103.     while (bt[idl].aa == 0) {
  104.         bt[idl].allzero = 0;
  105.         bt[idl].allone = 1;
  106.         bt[idl].aa = blocksz;
  107.         ans += blocksz;
  108.         idl++;
  109.     }
  110.     if (bt[idl].allzero) {
  111.         bt[idl].allzero = 0;
  112.         memset(bt[idl].a, 0, sizeof bt[idl].a);
  113.     } else if (bt[idl].allone) {
  114.         bt[idl].allone = 0;
  115.         for (int i = 0; i < blocksz; i++) {
  116.             bt[idl].a[i] = 1;
  117.         }
  118.     }
  119.     for (int i = 0; i < blocksz; i++) {
  120.         if (bt[idl].a[i] == 1) {
  121.             bt[idl].a[i] = 0;
  122.             bt[idl].aa--;
  123.             ans--;
  124.             return ;
  125.         } else {
  126.             bt[idl].aa++;
  127.             ans++;
  128.             bt[idl].a[i] = 1;
  129.         }
  130.     }
  131. }
  132.  
  133. main() {
  134.     int n;
  135.     scanf("%d", &n);
  136.     for (int i = 0; i < n; i++) {
  137.         cin >> s;
  138.         int pos;
  139.         scanf("%d", &pos);
  140.         if (s[0] == 'a') {
  141.             upd(pos);
  142.         } else {
  143.             upd1(pos);
  144.         }
  145.         printf("%d\n", ans);
  146.     }
  147. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top