Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstdlib>
- #include <vector>
- #include <set>
- #include <map>
- #include <cassert>
- #include <ctime>
- #include <cmath>
- #include <string>
- #include <cstring>
- #include <queue>
- using namespace std;
- #define f first
- #define s second
- #define mp make_pair
- #define pb push_back
- #define pii pair<int, int>
- #define vii vector<int, int>
- #define all(v) (v).begin(), (v).end()
- #define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
- const int maxn = 262144;
- const int inf = 2147483647;
- struct Tree {
- vector<int> a;
- vector<int> T;
- Tree(){
- T.clear();
- a.clear();
- }
- void update(int v, int x) {
- if (a.size() == 0) return;
- v = lower_bound(all(a), v) - a.begin() + 1;
- v += (int)a.size() - 1;
- T[v] += x;
- while (v > 1) {
- v >>= 1;
- T[v] = T[v + v] + T[v + v + 1];
- }
- }
- int findSum(int l, int r) {
- if (a.size() == 0) return 0;
- l = lower_bound(all(a), l) - a.begin() + 1;
- r = upper_bound(all(a), r) - a.begin();
- l += (int)a.size() - 1; r += (int)a.size() - 1;
- int res = 0;
- while (l <= r) {
- if (l & 1) res += T[l];
- if (!(r & 1)) res += T[r];
- l = (l + 1) >> 1; r = (r - 1) >> 1;
- }
- return res;
- }
- } T[maxn + maxn + 10];
- struct query {
- int type, x1, y1, x2, y2;
- query() {
- }
- query(int xx, int yy, int ttype = 0) {
- x1 = xx; y1 = yy;
- type = ttype;
- }
- query(int xx1, int yy1, int xx2, int yy2) {
- type = 2;
- x1 = xx1; y1 = yy1; x2 = xx2; y2 = yy2;
- }
- } q[maxn + 20];
- int X[maxn], Xn, Pn, qn;
- pii P[maxn];
- char s[100];
- void Build(int v, int sl, int sr, int l, int r) {
- for (int i = l; i <= r; ++i)
- assert(sl <= P[i].f && P[i].f <= sr);
- if (sl == sr) {
- for (int i = l; i <= r; ++i)
- T[v].a.pb(P[i].s);
- sort(all(T[v].a));
- T[v].a.erase(unique(all(T[v].a)), T[v].a.end());
- T[v].T.resize(T[v].a.size() * 2);
- return;
- }
- int mid = (sl + sr) >> 1;
- int pos = upper_bound(P, P + Pn, mp(mid, inf)) - P;
- Build(v + v, sl, mid, l, pos - 1);
- Build(v + v + 1, mid + 1, sr, pos, r);
- for (int i = l; i <= r; ++i)
- T[v].a.pb(P[i].s);
- sort(all(T[v].a));
- T[v].a.erase(unique(all(T[v].a)), T[v].a.end());
- T[v].T.resize(T[v].a.size() * 2);
- }
- void Add(int v, int y) {
- v += maxn - 1;
- if (T[v].findSum(y, y) == 1) {
- puts("ALREADY EXISTS");
- return;
- }
- while (v > 0) {
- T[v].update(y, 1);
- v >>= 1;
- }
- puts("ADDED");
- }
- void Delete(int v, int y) {
- v += maxn - 1;
- if (T[v].findSum(y, y) == 0) {
- puts("NOT FOUND");
- return;
- }
- while (v > 0) {
- T[v].update(y, -1);
- v >>= 1;
- }
- puts("DELETED");
- }
- int Count(int l, int r, int y1, int y2) {
- l += maxn - 1;
- r += maxn - 1;
- int res = 0;
- while (l <= r) {
- if (l & 1)
- res += T[l].findSum(y1, y2);
- if (!(r & 1))
- res += T[r].findSum(y1, y2);
- l = (l + 1) >> 1;
- r = (r - 1) >> 1;
- }
- return res;
- }
- int main() {
- #ifdef LOCAL
- freopen("in", "r", stdin);
- freopen("out", "w", stdout);
- #endif
- while (scanf("%s" , &s) == 1) {
- if (s[0] == 'A') {
- int x, y;
- scanf("%d%d\n", &x, &y);
- q[qn++] = query(x, y, 0);
- X[Xn++] = x;
- P[Pn++] = mp(x, y);
- } else
- if (s[0] == 'C')
- {
- int x1, y1, x2, y2;
- scanf("%d%d%d%d\n", &x1, &y1, &x2, &y2);
- q[qn++] = query(x1, y1, x2, y2);
- } else
- if (s[0] == 'D') {
- int x, y;
- scanf("%d%d\n", &x, &y);
- q[qn++] = query(x, y, 1);
- X[Xn++] = x;
- } else
- assert(false);
- }
- sort(X, X + Xn);
- Xn = unique(X, X + Xn) - X;
- for (int i = 0; i < Pn; ++i) {
- P[i].f = lower_bound(X, X + Xn, P[i].f) - X + 1;
- }
- sort(P, P + Pn);
- Pn = unique(P, P + Pn) - P;
- Build(1, 1, maxn, 0, Pn - 1);
- for (int i = 0; i < qn; ++i) {
- if (q[i].type == 0) {
- int x = lower_bound(X, X + Xn, q[i].x1) - X + 1;
- Add(x, q[i].y1);
- } else
- if (q[i].type == 1) {
- int x = lower_bound(X, X + Xn, q[i].x1) - X + 1;
- Delete(x, q[i].y1);
- } else
- if (q[i].type == 2) {
- int x1 = lower_bound(X, X + Xn, q[i].x1) - X + 1;
- int x2 = upper_bound(X, X + Xn, q[i].x2) - X;
- printf("%d\n", Count(x1, x2, q[i].y1, q[i].y2));
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment