Madiyar

acm.mipt.ru 120

Feb 24th, 2012
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.38 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <cassert>
  9. #include <ctime>
  10. #include <cmath>
  11. #include <string>
  12. #include <cstring>
  13. #include <queue>
  14.  
  15. using namespace std;
  16.  
  17. #define f first
  18. #define s second
  19. #define mp make_pair
  20. #define pb push_back
  21. #define pii pair<int, int>
  22. #define vii vector<int, int>
  23. #define all(v) (v).begin(), (v).end()
  24. #define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
  25.  
  26. const int maxn = 262144;
  27. const int inf = 2147483647;
  28.  
  29. struct Tree {
  30.  
  31.     vector<int> a;
  32.     vector<int> T;
  33.  
  34.     Tree(){
  35.         T.clear();
  36.         a.clear();
  37.     }          
  38.  
  39.     void update(int v, int x) {
  40.  
  41.         if (a.size() == 0) return;
  42.  
  43.         v = lower_bound(all(a), v) - a.begin() + 1;
  44.        
  45.         v += (int)a.size() - 1;
  46.  
  47.         T[v] += x;
  48.  
  49.         while (v > 1) {
  50.             v >>= 1;
  51.             T[v] = T[v + v] + T[v + v + 1];
  52.         }
  53.     }
  54.  
  55.     int findSum(int l, int r) {
  56.  
  57.         if (a.size() == 0) return 0;
  58.  
  59.         l = lower_bound(all(a), l) - a.begin() + 1;
  60.         r = upper_bound(all(a), r) - a.begin();
  61.  
  62.         l += (int)a.size() - 1; r += (int)a.size() - 1;
  63.  
  64.         int res = 0;
  65.  
  66.         while (l <= r) {
  67.             if (l & 1)  res += T[l];
  68.             if (!(r & 1)) res += T[r];
  69.             l = (l + 1) >> 1; r = (r - 1) >> 1;
  70.         }
  71.         return res;
  72.     }
  73.  
  74. } T[maxn + maxn + 10];
  75.  
  76. struct query {
  77.         int type, x1, y1, x2, y2;
  78.         query() {
  79.         }
  80.  
  81.         query(int xx, int yy, int ttype = 0) {
  82.                 x1 = xx; y1 = yy;
  83.                 type = ttype;
  84.         }
  85.  
  86.         query(int xx1, int yy1, int xx2, int yy2) {
  87.                 type = 2;
  88.                 x1 = xx1; y1 = yy1; x2 = xx2; y2 = yy2;
  89.         }
  90. } q[maxn + 20];
  91.  
  92. int X[maxn], Xn, Pn, qn;
  93. pii P[maxn];
  94. char s[100];
  95.  
  96.  
  97.  
  98.  
  99. void Build(int v, int sl, int sr, int l, int r) {
  100.  
  101.     for (int i = l; i <= r; ++i)
  102.         assert(sl <= P[i].f && P[i].f <= sr);
  103.    
  104.  
  105.     if (sl == sr) {
  106.  
  107.         for (int i = l; i <= r; ++i)
  108.             T[v].a.pb(P[i].s); 
  109.  
  110.         sort(all(T[v].a));
  111.  
  112.         T[v].a.erase(unique(all(T[v].a)), T[v].a.end());
  113.         T[v].T.resize(T[v].a.size() * 2);
  114.         return;
  115.     }
  116.  
  117.     int mid = (sl + sr) >> 1;
  118.     int pos = upper_bound(P, P + Pn, mp(mid, inf)) - P;
  119.  
  120.     Build(v + v, sl, mid, l, pos - 1);
  121.     Build(v + v + 1, mid + 1, sr, pos, r);                                        
  122.  
  123.     for (int i = l; i <= r; ++i)
  124.         T[v].a.pb(P[i].s);
  125.  
  126.     sort(all(T[v].a));
  127.     T[v].a.erase(unique(all(T[v].a)), T[v].a.end());
  128.     T[v].T.resize(T[v].a.size() * 2);
  129.  
  130. }
  131.  
  132. void Add(int v, int y) {
  133.  
  134.     v += maxn - 1;
  135.    
  136.     if (T[v].findSum(y, y) == 1) {
  137.         puts("ALREADY EXISTS");
  138.         return;
  139.     }
  140.  
  141.     while (v > 0) {
  142.         T[v].update(y, 1);
  143.         v >>= 1;       
  144.  
  145.     }
  146.  
  147.     puts("ADDED");
  148. }
  149.  
  150.  
  151. void Delete(int v, int y) {
  152.     v += maxn - 1;
  153.     if (T[v].findSum(y, y) == 0) {
  154.         puts("NOT FOUND");
  155.         return;
  156.     }
  157.  
  158.     while (v > 0) {
  159.         T[v].update(y, -1);
  160.         v >>= 1;       
  161.     }
  162.     puts("DELETED");
  163. }
  164.  
  165. int Count(int l, int r, int y1, int y2) {
  166.    
  167.     l += maxn - 1;
  168.     r += maxn - 1;
  169.     int res = 0;
  170.  
  171.     while (l <= r) {
  172.         if (l & 1)
  173.             res += T[l].findSum(y1, y2);
  174.         if (!(r & 1))
  175.             res += T[r].findSum(y1, y2);
  176.        
  177.         l = (l + 1) >> 1;
  178.         r = (r - 1) >> 1;
  179.     }
  180.  
  181.     return res;
  182.  
  183. }
  184.  
  185. int main() {
  186.  
  187.     #ifdef LOCAL
  188.         freopen("in", "r", stdin);
  189.         freopen("out", "w", stdout);
  190.     #endif
  191.  
  192.     while (scanf("%s" , &s) == 1) {
  193.  
  194.         if (s[0] == 'A') {
  195.             int x, y;
  196.             scanf("%d%d\n", &x, &y);
  197.             q[qn++] = query(x, y, 0);
  198.                                
  199.             X[Xn++] = x;
  200.             P[Pn++] = mp(x, y);
  201.            
  202.         } else
  203.         if (s[0] == 'C')
  204.         {
  205.             int x1, y1, x2, y2;
  206.             scanf("%d%d%d%d\n", &x1, &y1, &x2, &y2);
  207.             q[qn++] = query(x1, y1, x2, y2);
  208.         } else
  209.         if (s[0] == 'D') {
  210.             int x, y;
  211.             scanf("%d%d\n", &x, &y);
  212.             q[qn++] = query(x, y, 1);
  213.             X[Xn++] = x;
  214.         } else
  215.         assert(false);
  216.     }
  217.  
  218.     sort(X, X + Xn);
  219.     Xn = unique(X, X + Xn) - X;
  220.  
  221.     for (int i = 0; i < Pn; ++i) {
  222.         P[i].f = lower_bound(X, X + Xn, P[i].f) - X + 1;
  223.     }
  224.  
  225.     sort(P, P + Pn);
  226.  
  227.     Pn = unique(P, P + Pn) - P;
  228.  
  229.     Build(1, 1, maxn, 0, Pn - 1);
  230.  
  231.     for (int i = 0; i < qn; ++i) {
  232.         if (q[i].type == 0) {
  233.             int x = lower_bound(X, X + Xn, q[i].x1) - X + 1;
  234.             Add(x, q[i].y1);
  235.         } else
  236.         if (q[i].type == 1) {
  237.             int x = lower_bound(X, X + Xn, q[i].x1) - X + 1;
  238.             Delete(x, q[i].y1);
  239.         } else
  240.         if (q[i].type == 2) {
  241.             int x1 = lower_bound(X, X + Xn, q[i].x1) - X + 1;
  242.             int x2 = upper_bound(X, X + Xn, q[i].x2) - X;
  243.             printf("%d\n", Count(x1, x2, q[i].y1, q[i].y2));
  244.         }              
  245.     }
  246.  
  247.  
  248.     return 0;
  249. }
Advertisement
Add Comment
Please, Sign In to add comment