제출 #122649

#제출 시각아이디문제언어결과실행 시간메모리
122649luciocfRuka (COI15_ruka)C++17
44 / 100
2063 ms20928 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") const int maxn = 1e5+10; struct node { node *l, *r; int v, w, sz; node(int vv) { v = vv, w = rand(), sz = 1; l = r = NULL; } }; typedef node*& node_t; stack<int> stk_x[2], stk_y[2]; int vx[maxn], vy[maxn]; int sz(node *t) {return (t ? t->sz : 0);} void op(node *t) { if (t) t->sz = sz(t->l)+sz(t->r)+1; } void split(node *t, node_t l, node_t r, int v) { if (!t) return void(l=r=NULL); if (t->v > v) split(t->l, l, t->l, v), r = t; else split(t->r, t->r, r, v), l = t; op(t); } void merge(node_t t, node *l, node *r) { if (!l || !r) t = (l ? l : r); else if (l->w > r->w) merge(l->r, l->r, r), t = l; else merge(r->l, l, r->l), t = r; op(t); } void insert(node_t t, node *aux) { if (!t) t = aux; else if (aux->w > t->w) split(t, aux->l, aux->r, aux->v), t = aux; else insert((aux->v > t->v ? t->r : t->l), aux); op(t); } void erase(node_t t, int v) { if (t->v == v) merge(t, t->l, t->r); else erase((v > t->v ? t->r : t->l), v); op(t); } int query(node *t, int v) { if (!t) return 0; if (t->v < v) return (1+sz(t->l)+query(t->r, v)); return query(t->l, v); } int main(void) { int n; scanf("%d", &n); int pref_x = 1, pref_y = 1; node *root_x[2], *root_y[2]; root_x[0] = root_x[1] = root_y[0] = root_y[1] = NULL; for (int i = 1; i <= n; i++) { scanf("%d %d", &vx[i], &vy[i]); pref_x += vx[i], pref_y += vy[i]; } for (int i = n; i > 1; i--) { pref_x -= vx[i]; pref_y -= vy[i]; int mn = min(pref_x, pref_x+vx[i]), mx = max(pref_x, pref_x+vx[i]); node *aux1 = new node(mn), *aux2 = new node(mx); insert(root_x[0], aux1); insert(root_x[1], aux2); stk_x[0].push(mn); stk_x[1].push(mx); mn = min(pref_y, pref_y+vy[i]), mx = max(pref_y, pref_y+vy[i]); aux1 = new node(mn), aux2 = new node(mx); insert(root_y[0], aux1); insert(root_y[1], aux2); stk_y[0].push(mn); stk_y[1].push(mx); } pref_x = 1, pref_y = 1; int ptr = 1, ans = 0, delta_x = 0, delta_y = 0; if (min(1+vx[1], 1) < 0 && max(1+vx[1], 1) > 0) ans++; if (min(1+vy[1], 1) < 0 && max(1+vy[1], 1) > 0) ans++; int m; scanf("%d", &m); for (int i = 1; i <= m; i++) { char op; scanf(" %c", &op); if (op == 'B' && ptr != 1) { int mn = min(pref_x, pref_x+vx[ptr]), mx = max(pref_x, pref_x+vx[ptr]); if (mn < 0 && mx > 0) ans--; node *aux1 = new node(mn-delta_x), *aux2 = new node(mx-delta_x); insert(root_x[0], aux1); insert(root_x[1], aux2); stk_x[0].push(mn-delta_x); stk_x[1].push(mx-delta_x); mn = min(pref_y, pref_y+vy[ptr]), mx = max(pref_y, pref_y+vy[ptr]); if (mn < 0 && mx > 0) ans--; aux1 = new node(mn-delta_y), aux2 = new node(mx-delta_y); insert(root_y[0], aux1); insert(root_y[1], aux2); stk_y[0].push(mn-delta_y); stk_y[1].push(mx-delta_y); ptr--; pref_x -= vx[ptr], pref_y -= vy[ptr]; } else if (op == 'F' && ptr != n) { int mn = stk_x[0].top(), mx = stk_x[1].top(); stk_x[0].pop(); stk_x[1].pop(); erase(root_x[0], mn); erase(root_x[1], mx); mn = stk_y[0].top(), mx = stk_y[1].top(); stk_y[0].pop(); stk_y[1].pop(); erase(root_y[0], mn); erase(root_y[1], mx); pref_x += vx[ptr], pref_y += vy[ptr], ptr++; if (min(pref_x, pref_x+vx[ptr]) < 0 && max(pref_x, pref_x+vx[ptr]) > 0) ans++; if (min(pref_y, pref_y+vy[ptr]) < 0 && max(pref_y, pref_y+vy[ptr]) > 0) ans++; } else if (op == 'C') { int nx, ny; scanf("%d %d", &nx, &ny); if (min(pref_x, pref_x+vx[ptr]) < 0 && max(pref_x, pref_x+vx[ptr]) > 0) ans--; if (min(pref_y, pref_y+vy[ptr]) < 0 && max(pref_y, pref_y+vy[ptr]) > 0) ans--; delta_x += (nx - vx[ptr]), delta_y += (ny - vy[ptr]); vx[ptr] = nx, vy[ptr] = ny; if (min(pref_x, pref_x+vx[ptr]) < 0 && max(pref_x, pref_x+vx[ptr]) > 0) ans++; if (min(pref_y, pref_y+vy[ptr]) < 0 && max(pref_y, pref_y+vy[ptr]) > 0) ans++; } else if (op == 'Q') { int tot = ans + query(root_x[0], -delta_x) + query(root_y[0], -delta_y); tot -= (query(root_x[1], -delta_x) + query(root_y[1], -delta_y)); printf("%d\n", tot); } } }

컴파일 시 표준 에러 (stderr) 메시지

ruka.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
ruka.cpp:7:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
ruka.cpp: In function 'int main()':
ruka.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
ruka.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &vx[i], &vy[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
ruka.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &op);
   ~~~~~^~~~~~~~~~~~
ruka.cpp:169:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &nx, &ny);
    ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...