제출 #154682

#제출 시각아이디문제언어결과실행 시간메모리
154682stefdascaRuka (COI15_ruka)C++14
44 / 100
2100 ms45280 KiB
#include<bits/stdc++.h> #define fi first #pragma GCC optimize("Ofast") #define se second using namespace std; int n, q, buk; char tip; deque<int>mod; int poz = 1; int prefixx[100002], prefixy[100002], ans[100002]; int Le, Ri; pair<int, int> dir[100002], xx[100002], yy[100002]; vector<vector<int> >aint[2]; int last_answer; struct st { char c; int a, b; }; st vov[300002]; void build(int nod, int st, int dr) { aint[0][nod].resize(dr - st + 1), aint[1][nod].resize(dr - st + 1); if(st == dr) { aint[0][nod][0] = (xx[st].se); aint[1][nod][0] = (yy[st].se); return; } int mid = (st + dr) / 2; build(nod << 1, st, mid); build(nod << 1|1, mid+1, dr); int pa = 0; int pb = 0; int pop = 0; while(pa < aint[0][nod << 1].size() && pb < aint[0][nod << 1|1].size()) { if(aint[0][nod << 1][pa] <= aint[0][nod << 1|1][pb]) aint[0][nod][pop] = aint[0][nod << 1][pa], ++pa; else aint[0][nod][pop] = aint[0][nod << 1|1][pb], ++pb; ++pop; } while(pa < aint[0][nod << 1].size()) aint[0][nod][pop] = aint[0][nod << 1][pa], ++pa, ++pop; while(pb < aint[0][nod << 1|1].size()) aint[0][nod][pop] = aint[0][nod << 1|1][pb], ++pb, pop++; pa = 0; pb = 0; pop = 0; while(pa < aint[1][nod << 1].size() && pb < aint[1][nod << 1|1].size()) { if(aint[1][nod << 1][pa] <= aint[1][nod << 1|1][pb]) aint[1][nod][pop] = aint[1][nod << 1][pa], ++pa, ++pop; else aint[1][nod][pop] = aint[1][nod << 1|1][pb], ++pb, ++pop; } while(pa < aint[1][nod << 1].size()) aint[1][nod][pop] = aint[1][nod << 1][pa], ++pa, ++pop; while(pb < aint[1][nod << 1|1].size()) aint[1][nod][pop] = aint[1][nod << 1|1][pb], ++pb, ++pop; } int orgx, orgy; void rebuild(int nrq, int start_poz) { Le = Ri = start_poz; for(int i = nrq; i <= q; ++i) { if(vov[i].c == 'B') { start_poz = max(1, start_poz - 1); Le = min(Le, start_poz); } if(vov[i].c == 'F') { start_poz = min(n, start_poz + 1); Ri = max(Ri, start_poz); } if(Ri - Le + 1 >= 3000) break; } mod.clear(); prefixx[0] = 1; prefixy[0] = 1; for(int i = max(1, start_poz - 3500); i <= n; ++i) { ans[i] = ans[i-1]; if(prefixx[i-1] > 0 && prefixx[i-1] + dir[i].fi < 0) ++ans[i]; if(prefixx[i-1] < 0 && prefixx[i-1] + dir[i].fi > 0) ++ans[i]; if(prefixy[i-1] > 0 && prefixy[i-1] + dir[i].se < 0) ++ans[i]; if(prefixy[i-1] < 0 && prefixy[i-1] + dir[i].se > 0) ++ans[i]; prefixx[i] = prefixx[i-1] + dir[i].fi; prefixy[i] = prefixy[i-1] + dir[i].se; } for(int i = Le; i <= Ri; ++i) mod.push_back(i); orgx = prefixx[mod.back()]; orgy = prefixy[mod.back()]; for(int i = 1; i <= n - (Ri + 1) + 1; ++i) { xx[i] = {max(prefixx[Ri + i], prefixx[Ri + i - 1]), min(prefixx[Ri + i], prefixx[Ri + i - 1])}; yy[i] = {max(prefixy[Ri + i], prefixy[Ri + i - 1]), min(prefixy[Ri + i], prefixy[Ri + i - 1])}; } sort(xx + 1, xx + n - (Ri + 1) + 1 + 1); sort(yy + 1, yy + n - (Ri + 1) + 1 + 1); if(Ri != n) build(1, 1, n - (Ri + 1) + 1); } int queryx(int nod, int st, int dr, int L, int R, int threshold) { if(dr < L || st > R) return 0; if(L <= st && dr <= R) { int st1 = 0; int dr1 = aint[0][nod].size() - 1; int ans = -1; if(aint[0][nod].back() < threshold) return aint[0][nod].size(); if(aint[0][nod][0] >= threshold) return 0; while(st1 <= dr1) { int mid = (st1 + dr1) / 2; if(aint[0][nod][mid] < threshold) ans = mid, st1 = mid + 1; else dr1 = mid - 1; } return (ans + 1); } int mid = (st + dr) / 2; return queryx(nod << 1, st, mid, L, R, threshold) + queryx(nod << 1|1, mid+1, dr, L, R, threshold); } int queryy(int nod, int st, int dr, int L, int R, int threshold) { if(dr < L || st > R) return 0; if(L <= st && dr <= R) { int st1 = 0; int dr1 = aint[1][nod].size() - 1; int ans = -1; if(aint[1][nod].back() < threshold) return aint[0][nod].size(); if(aint[1][nod][0] >= threshold) return 0; while(st1 <= dr1) { int mid = (st1 + dr1) / 2; if(aint[1][nod][mid] < threshold) ans = mid, st1 = mid + 1; else dr1 = mid - 1; } return (ans + 1); } int mid = (st + dr) / 2; return queryy(nod << 1, st, mid, L, R, threshold) + queryy(nod << 1|1, mid+1, dr, L, R, threshold); } int solve(int minii) { int start = minii - 1; int sol = ans[start]; int sumx = prefixx[start]; int sumy = prefixy[start]; bool op = 0; for(int i = minii - mod[0]; i < mod.size(); ++i) { op = 1; if(sumx > 0 && sumx + dir[mod[i]].fi < 0) ++sol; if(sumx < 0 && sumx + dir[mod[i]].fi > 0) ++sol; if(sumy > 0 && sumy + dir[mod[i]].se < 0) ++sol; if(sumy < 0 && sumy + dir[mod[i]].se > 0) ++sol; start = mod[i]; sumx += dir[mod[i]].fi; sumy += dir[mod[i]].se; prefixx[mod[i]] = sumx; prefixy[mod[i]] = sumy; ans[mod[i]] = sol; } if(Ri != n) { int st = 1; int dr = n - Ri; int ans = 0; while(st <= dr) { int mid = (st + dr) / 2; if(xx[mid].fi >= -(sumx - orgx)) ans = mid, dr = mid - 1; else st = mid + 1; } if(ans != 0) sol += queryx(1, 1, n - Ri, ans, n - Ri, -(sumx - orgx)); st = 1; dr = n - Ri; ans = 0; while(st <= dr) { int mid = (st + dr) / 2; if(yy[mid].fi >= -(sumy - orgy)) ans = mid, dr = mid - 1; else st = mid + 1; } if(ans != 0) sol += queryy(1, 1, n - Ri, ans, n - Ri, -(sumy - orgy)); } return sol; } void solvegood() { int lq = 0; for(int i = 1; i <= q; ++i) { cin >> vov[i].c; if(vov[i].c == 'C') cin >> vov[i].a >> vov[i].b; if(vov[i].c == 'Q') lq = i; } rebuild(1, poz); last_answer = -1; int minii = mod.back() + 1; for(int i = 1; i <= lq; ++i) { char tip = vov[i].c; if(tip == 'B') poz = max(1, poz - 1); if(tip == 'F') poz = min(poz + 1, n); if(tip == 'Q') { if(last_answer == -1) last_answer = solve(minii); cout << last_answer << '\n'; minii = mod.back() + 1; } if(tip == 'C') { int a = vov[i].a, b = vov[i].b; dir[poz] = {a, b}; minii = min(minii, poz); last_answer = -1; } if(poz < Le || poz > Ri) { last_answer = -1; rebuild(i, poz); minii = mod.back() + 1; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i = 1; i <= n; ++i) cin >> dir[i].fi >> dir[i].se; cin >> q; aint[0].resize(280000); aint[1].resize(280000); solvegood(); return 0; }

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

ruka.cpp: In function 'void build(int, int, int)':
ruka.cpp:36:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pa < aint[0][nod << 1].size() && pb < aint[0][nod << 1|1].size())
           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:36:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pa < aint[0][nod << 1].size() && pb < aint[0][nod << 1|1].size())
                                            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:44:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pa < aint[0][nod << 1].size())
           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:46:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pb < aint[0][nod << 1|1].size())
           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:51:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pa < aint[1][nod << 1].size() && pb < aint[1][nod << 1|1].size())
           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:51:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pa < aint[1][nod << 1].size() && pb < aint[1][nod << 1|1].size())
                                            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:58:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pa < aint[1][nod << 1].size())
           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:60:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pb < aint[1][nod << 1|1].size())
           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp: In function 'int solve(int)':
ruka.cpp:171:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = minii - mod[0]; i < mod.size(); ++i)
                                 ~~^~~~~~~~~~~~
ruka.cpp:170:10: warning: variable 'op' set but not used [-Wunused-but-set-variable]
     bool op = 0;
          ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...