Submission #614201

#TimeUsernameProblemLanguageResultExecution timeMemory
614201GusterGoose27Ruka (COI15_ruka)C++11
44 / 100
2067 ms6048 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pii; const ll MAXN = 1e5; ll n, q; const ll BSIZE = 301; const ll MAXBLOCKS = 333; ll num_blocks; ll numsx[MAXN]; ll numsy[MAXN]; pii vecs[MAXN]; ll max(ll a, int b) { if (a > b) return a; return b; } ll sign(ll v) { if (v == 0) return 0; if (v < 0) return -1; return 1; } class Block { public: vector<ll> xstart; vector<ll> xend; vector<ll> ystart; vector<ll> yend; ll shiftx = 0; ll shifty = 0; ll lp, rp; Block() {} Block(ll lv, ll rv) { lp = lv; rp = rv; make(); } void make() { xstart.clear(); xend.clear(); ystart.clear(); yend.clear(); for (ll i = lp; i <= rp; i++) { if (i > lp) { ll x1 = numsx[i]; ll x2 = numsx[i-1]; ll y1 = numsy[i]; ll y2 = numsy[i-1]; ll mnx = min(x1, x2); ll mxx = max(x1, x2); ll mny = min(y1, y2); ll mxy = max(y1, y2); xstart.push_back(-mxx); xend.push_back(-mnx); ystart.push_back(-mxy); yend.push_back(-mny); } } sort(xstart.begin(), xstart.end()); sort(ystart.begin(), ystart.end()); sort(xend.begin(), xend.end()); sort(yend.begin(), yend.end()); } ll bs(vector<ll> &v, ll pos) { ll mn = -1; ll mx = v.size(); while (mx > mn+1) { ll cur = (mn+mx)/2; if (v[cur] < pos) mn = cur; else mx = cur; assert(v[cur] != pos); } return mn+1; } ll get() { return bs(xstart, shiftx)+bs(ystart, shifty)-bs(xend, shiftx)-bs(yend, shifty); } void upd(ll l, ll r, ll vx, ll vy) { for (ll i = lp; i <= rp; i++) { numsx[i] += shiftx; numsy[i] += shifty; if (l <= i && i <= r) { numsx[i] += vx; numsy[i] += vy; } } shiftx = 0; shifty = 0; make(); } }; Block blocks[MAXBLOCKS]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; num_blocks = ceil((1.0*(n+1))/BSIZE); ll curx = 1; ll cury = 1; for (ll i = 0; i < n; i++) { numsx[i] = curx; numsy[i] = cury; ll x, y; cin >> x >> y; curx += x; cury += y; vecs[i] = pii(x, y); } numsx[n] = curx; numsy[n] = cury; for (ll i = 0; i < num_blocks; i++) { blocks[i] = Block(BSIZE*i, min(BSIZE*(i+1)-1, n)); } ll pos = 0; cin >> q; for (ll i = 0; i < q; i++) { char c; cin >> c; if (c == 'Q') { ll ans = 0; for (ll j = 0; j < num_blocks; j++) { ans += blocks[j].get(); if (j < num_blocks-1) { ll x1 = numsx[blocks[j].rp]+blocks[j].shiftx; ll y1 = numsy[blocks[j].rp]+blocks[j].shifty; ll x2 = numsx[blocks[j+1].lp]+blocks[j+1].shiftx; ll y2 = numsy[blocks[j+1].lp]+blocks[j+1].shifty; ans += (sign(x1) != sign(x2)) + (sign(y1) != sign(y2)); } } cout << ans << "\n"; } if (c == 'B') { pos = max(pos-1, 0); } if (c == 'F') { pos = min(n-1, pos+1); } if (c == 'C') { ll x, y; cin >> x >> y; ll xsh = x-vecs[pos].first; ll ysh = y-vecs[pos].second; vecs[pos] = pii(x, y); for (ll j = 0; j < num_blocks; j++) { if (blocks[j].rp <= pos) continue; if (blocks[j].lp <= pos) { blocks[j].upd(pos+1, blocks[j].rp, xsh, ysh); } else { blocks[j].shiftx += xsh; blocks[j].shifty += ysh; } } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...