Submission #155699

#TimeUsernameProblemLanguageResultExecution timeMemory
155699FischerRuka (COI15_ruka)C++14
100 / 100
1218 ms13780 KiB
#include <bits/stdc++.h> #include <unordered_map> using namespace std; const int maxn = 1e5 + 10; const int maxS = 2e8 + 10; int axis_x = maxS/2, axis_y = maxS/2; int n, q; unordered_map<int, int> ft[2]; int x[maxn], y[maxn]; stack<int> Qx, Qy; int left_ans; void update(int t, int pos, int v) { pos += maxS/2; while (pos < maxS) { ft[t][pos] += v; pos += pos&-pos; } } int query(int t, int pos) { pos += t == 0 ? axis_x : axis_y;; int ans = 0; while (pos > 0) { ans += ft[t][pos]; pos -= pos&-pos; } return ans; } void add_x(int l, int r) { if (l > r) swap(l, r); Qx.push(l); Qx.push(r); update(0, r+1, -1); update(0, l, 1); } void add_y(int l, int r) { if (l > r) swap(l, r); Qy.push(l); Qy.push(r); update(1, r+1, -1); update(1, l, 1); } void remove_x() { int l = Qx.top(); Qx.pop(); int r = Qx.top(); Qx.pop(); if (l > r) swap(l, r); update(0, r+1, 1); update(0, l, -1); } void remove_y() { int l = Qy.top(); Qy.pop(); int r = Qy.top(); Qy.pop(); if (l > r) swap(l, r); update(1, r+1, 1); update(1, l, -1); } int sum_left_x, sum_left_y; int sum_right_x, sum_right_y; int cur_position; void setup(int x[], int y[]) { sum_left_x = 1; sum_left_y = 1; sum_right_x = accumulate(x, x+n+1, 0); sum_right_y = accumulate(y, y+n+1, 0); for (int i = n; i >= 1; --i) { add_x(sum_right_x, sum_right_x - x[i]); add_y(sum_right_y, sum_right_y - y[i]); sum_right_x -= x[i]; sum_right_y -= y[i]; } cur_position = 1; } void next_position() { remove_x(); if ((sum_left_x^(sum_left_x + x[cur_position])) < 0) { left_ans += 1; } sum_left_x += x[cur_position]; sum_right_x += x[cur_position]; remove_y(); if ((sum_left_y^(sum_left_y + y[cur_position])) < 0) { left_ans += 1; } sum_left_y += y[cur_position]; sum_right_y += y[cur_position]; cur_position += 1; } void prev_position() { cur_position -= 1; add_x(sum_right_x, sum_right_x - x[cur_position]); if ((sum_left_x ^ (sum_left_x - x[cur_position])) < 0) { left_ans -= 1; } sum_left_x -= x[cur_position]; sum_right_x -= x[cur_position]; add_y(sum_right_y, sum_right_y - y[cur_position]); if ((sum_left_y ^ (sum_left_y - y[cur_position])) < 0) { left_ans -= 1; } sum_left_y -= y[cur_position]; sum_right_y -= y[cur_position]; } void make_change(int _x, int _y) { remove_x(); sum_right_x += x[cur_position]; add_x(sum_right_x, sum_right_x - _x); sum_right_x -= _x; axis_x += x[cur_position] - _x; x[cur_position] = _x; remove_y(); sum_right_y += y[cur_position]; add_y(sum_right_y, sum_right_y - _y); sum_right_y -= _y; axis_y += y[cur_position] - _y; y[cur_position] = _y; } int response() { return query(0, 0) + query(1, 0) + left_ans; } int main() { cin >> n; x[0] = y[0] = 1; for (int i = 1; i <= n; ++i) { cin >> x[i] >> y[i]; } setup(x, y); cin >> q; cin.get(); while (q--) { int type = cin.get(); if (type == 'Q') { cout << response() << endl; } else if (type == 'F') { if (cur_position < n) { next_position(); } } else if (type == 'B') { if (cur_position > 1) { prev_position(); } } else { int x, y; cin >> x >> y; make_change(x, y); } cin.get(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...