SHARE
TWEET

dmopc17c4p6 err

a guest Feb 18th, 2020 139 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. typedef double D;
  5. typedef vector<int> VI;
  6. typedef set<int> SI;
  7. typedef map<int, int> MII;
  8. typedef pair<int,int> PII;
  9.  
  10. #define MP make_pair
  11. #define A first
  12. #define B second
  13.  
  14. #define PB push_back
  15. #define FR(i, a, b) for(int i=(a); i<(b); i++)
  16. #define FOR(i, n) FR(i, 0, n)
  17. #define EACH(it,X) for(__typeof((X).begin()) it=(X).begin(); it!=(X).end(); ++it)
  18.  
  19. template <typename T> inline void SetMin(T &a, T b) {if(b < a) a = b;}
  20. template <typename T> inline void SetMax(T &a, T b) {if(b > a) a = b;}
  21.  
  22. const D EPS = 1e-9;
  23. int EQ(D a, D b) {return fabs(a - b) < EPS;}
  24.  
  25. typedef complex<D> P;
  26. #define X real
  27. #define Y imag
  28. P GetPoint() {  D x, y; cin >> x >> y; return P(x, y);}
  29. void ShowPoint(P p) {cout << X(p) << "," << Y(p) << "\n";}
  30. D Cross(P a, P b) {return Y(conj(a) * b);}
  31. D Dot(P a, P b) {return X(conj(a) * b);}
  32.  
  33. const LL M = 1000000007LL;
  34. void Add(LL &a, LL b) {a = (a + b) % M;}
  35. void Mul(LL &a, LL b) {a = (a * b) % M;}
  36. LL Sum(LL a, LL b) {return (a + b) % M;}
  37. LL Prod(LL a, LL b) {return (a * b) % M;}
  38.  
  39. namespace IO {
  40.    const int BUF = 32768;
  41.    FILE *in = stdin;
  42.    int ipos = BUF;
  43.    char inbuf [BUF];
  44.    inline void init (const char *namein) {
  45.        in = fopen (namein, "r");
  46.    }
  47.  
  48.    inline char nextc (bool adv = true) {
  49.        if (ipos == BUF) {
  50.            fread (inbuf, sizeof (char), BUF, in);
  51.            ipos = 0;
  52.        }
  53.        return inbuf [adv ? ipos++ : ipos];
  54.    }
  55.  
  56.    inline void read (int &num) {
  57.        while (nextc (false) != '-' && (nextc (false) < '0' || nextc (false) > '9')) {
  58.            ipos++;
  59.        }
  60.  
  61.        bool neg = false;
  62.        if (nextc (false) == '-') {
  63.            neg = true;
  64.            ipos++;
  65.        }
  66.  
  67.        for (num = 0; nextc (false) >= '0' && nextc (false) <= '9';) {
  68.            num = num * 10 + nextc () - '0';
  69.        }
  70.  
  71.        if (neg) num = -num;
  72.    }
  73.  
  74.    inline void readch (char &ch) {
  75.        while (nextc (false) < 'A' || nextc (false) > 'Z') {
  76.            ipos++;
  77.        }
  78.  
  79.        ch = nextc();
  80.  
  81.    }
  82.  
  83. }
  84.  
  85. struct node{
  86.   int m, a, k, i, ma, ak, ki, mak, aki, maki;
  87.   node() {
  88.     m = a = k = i = ma = ak = ki = mak = aki = maki = 0;
  89.   }
  90. };
  91.  
  92. const int DEP = 18;
  93. const int SIZ = 1<<DEP;
  94.  
  95. node tree[SIZ * 2];
  96. int len[SIZ * 2];
  97. char marked[SIZ * 2];
  98.  
  99. int n, q;
  100.  
  101. void MarkRange(int p, char ch) {
  102.   tree[p] = node();
  103.   if(ch == 'M') tree[p].m = len[p];
  104.   if(ch == 'A') tree[p].a = len[p];
  105.   if(ch == 'K') tree[p].k = len[p];
  106.   if(ch == 'I') tree[p].i = len[p];
  107.   marked[p] = ch;
  108. }
  109.  
  110. void Down(int p) {
  111.   if(marked[p] != 0) {
  112.     MarkRange(p * 2, marked[p]);
  113.     MarkRange(p * 2 + 1, marked[p]);
  114.     marked[p] = 0;
  115.   }
  116. }
  117.  
  118. inline void Moo(int &res, int &a, int &b) {
  119.   int k = min(a, b);
  120.   res += k;
  121.   a -= k;
  122.   b -= k;
  123. }
  124.  
  125. void Merge(node &res, node a, node b) {
  126.   res = node();
  127.   Moo(res.maki, a.mak, b.i);
  128.   Moo(res.maki, a.ma, b.ki);
  129.   Moo(res.maki, a.m, b.aki);
  130.   Moo(res.mak, a.ma, b.k);
  131.   Moo(res.mak, a.m, b.ak);
  132.   Moo(res.aki, a.ak, b.i);
  133.   Moo(res.aki, a.a, b.ki);
  134.   Moo(res.ak, a.a, b.k);
  135.   Moo(res.ki, a.k, b.i);
  136.   Moo(res.ma, a.m, b.a);
  137.   res.m += a.m + b.m;
  138.   res.a += a.a + b.a;
  139.   res.k += a.k + b.k;
  140.   res.i += a.i + b.i;
  141.   res.ma += a.ma + b.ma;
  142.   res.ak += a.ak + b.ak;
  143.   res.ki += a.ki + b.ki;
  144.   res.mak += a.mak + b.mak;
  145.   res.aki += a.aki + b.aki;
  146.   res.maki += a.maki + b.maki;
  147. }
  148.  
  149. node Query(int p, int l, int r, int l1, int r1) {
  150.   if(l == l1 && r == r1) {
  151.     return tree[p];
  152.   } else {
  153.     node res;
  154.     Down(p);
  155.     int mid = (l + r) / 2;
  156.     if(r1 <= mid) res = Query(p * 2, l, mid, l1, r1);
  157.     else if(mid < l1) res = Query(p * 2 + 1, mid + 1, r, l1, r1);
  158.     else {
  159.       Merge(res, Query(p * 2, l, mid, l1, mid), Query(p * 2 + 1, mid + 1, r, mid + 1, r1));
  160.     }
  161.     return res;
  162.   }
  163. }
  164.  
  165.  
  166. void SetRange(int p, int l, int r, int l1, int r1, char ch) {
  167.   if(l == l1 && r == r1) {
  168.     MarkRange(p, ch);
  169.   } else {
  170.     int mid = (l + r) / 2;
  171.     Down(p);
  172.     if(r1 <= mid) SetRange(p * 2, l, mid, l1, r1, ch);
  173.     else if(mid < l1) SetRange(p * 2 + 1, mid + 1, r, l1, r1, ch);
  174.     else {
  175.       SetRange(p * 2, l, mid, l1, mid, ch);
  176.       SetRange(p * 2 + 1, mid + 1, r, mid + 1, r1, ch);
  177.     }
  178.     Merge(tree[p], tree[p * 2], tree[p * 2 + 1]);
  179.   }
  180. }
  181.  
  182. int main() {
  183.   memset(marked, 0, sizeof(marked));
  184.   FOR(i, SIZ) {
  185.     len[SIZ + i] = 1;
  186.   }
  187.   for(int i = SIZ - 1; i > 0; --i) {
  188.     len[i] = len[i * 2] + len[i * 2 + 1];
  189.   }
  190.   IO::read(n);
  191.   IO::read(q);
  192.   FOR(i, q) {
  193.     int cmd, l, r;
  194.     IO::read(cmd);
  195.     IO::read(l);
  196.     IO::read(r);
  197. //printf("%d %d %d\n", cmd, l, r); fflush(stdout);
  198.     if(cmd == 2) {
  199.       printf("%d\n", Query(1, 1, SIZ, l, r).maki);
  200.     } else {
  201.       char ch;
  202.       IO::readch(ch);
  203. //printf("%c\n", ch);
  204.       SetRange(1, 1, SIZ, l, r, ch);
  205.     }
  206.   }
  207.   return 0;
  208. }
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