Submission #614207

#TimeUsernameProblemLanguageResultExecution timeMemory
614207GusterGoose27Ruka (COI15_ruka)C++11
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int; typedef pair<int, int> pii; const int MAXN = 1e5; int n, q; const int BSIZE = 301; const int MAXBLOCKS = 333; int num_blocks; int numsx[MAXN]; int numsy[MAXN]; pii vecs[MAXN]; int max(int a, int b) { if (a > b) return a; return b; } int sign(int v) { if (v == 0) return 0; if (v < 0) return -1; return 1; } class Block { public: vector<int> xstart; vector<int> xend; vector<int> ystart; vector<int> yend; int shiftx = 0; int shifty = 0; int lp, rp; Block() {} Block(int lv, int rv) { lp = lv; rp = rv; make(); } void make() { xstart.clear(); xend.clear(); ystart.clear(); yend.clear(); for (int i = lp; i <= rp; i++) { if (i > lp) { int x1 = numsx[i]; int x2 = numsx[i-1]; int y1 = numsy[i]; int y2 = numsy[i-1]; int mnx = min(x1, x2); int mxx = max(x1, x2); int mny = min(y1, y2); int 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()); } int bs(vector<int> &v, int pos) { int mn = -1; int mx = v.size(); while (mx > mn+1) { int cur = (mn+mx)/2; if (v[cur] < pos) mn = cur; else mx = cur; assert(v[cur] != pos); } return mn+1; } int get() { return bs(xstart, shiftx)+bs(ystart, shifty)-bs(xend, shiftx)-bs(yend, shifty); } void upd(int l, int r, int vx, int vy) { xstart.clear(); xend.clear(); ystart.clear(); yend.clear(); for (int i = lp; i <= rp; i++) { numsx[i] += shiftx; numsy[i] += shifty; if (l <= i && i <= r) { numsx[i] += vx; numsy[i] += vy; } if (i > lp) { int x1 = numsx[i]; int x2 = numsx[i-1]; int y1 = numsy[i]; int y2 = numsy[i-1]; int mnx = min(x1, x2); int mxx = max(x1, x2); int mny = min(y1, y2); int 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()); } }; Block blocks[MAXBLOCKS]; int main() { ios_base::sync_with_stdio(false); cin.tie(NUint); cin >> n; num_blocks = ceil((1.0*(n+1))/BSIZE); int curx = 1; int cury = 1; for (int i = 0; i < n; i++) { numsx[i] = curx; numsy[i] = cury; int x, y; cin >> x >> y; curx += x; cury += y; vecs[i] = pii(x, y); } numsx[n] = curx; numsy[n] = cury; for (int i = 0; i < num_blocks; i++) { blocks[i] = Block(BSIZE*i, min(BSIZE*(i+1)-1, n)); } int pos = 0; cin >> q; for (int i = 0; i < q; i++) { char c; cin >> c; if (c == 'Q') { int ans = 0; for (int j = 0; j < num_blocks; j++) { ans += blocks[j].get(); if (j < num_blocks-1) { int x1 = numsx[blocks[j].rp]+blocks[j].shiftx; int y1 = numsy[blocks[j].rp]+blocks[j].shifty; int x2 = numsx[blocks[j+1].lp]+blocks[j+1].shiftx; int 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') { int x, y; cin >> x >> y; int xsh = x-vecs[pos].first; int ysh = y-vecs[pos].second; vecs[pos] = pii(x, y); for (int 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; } } } } }

Compilation message (stderr)

ruka.cpp:5:19: error: declaration does not declare anything [-fpermissive]
    5 | typedef long long int;
      |                   ^~~
ruka.cpp: In function 'int main()':
ruka.cpp:120:44: error: 'NUint' was not declared in this scope
  120 |  ios_base::sync_with_stdio(false); cin.tie(NUint);
      |                                            ^~~~~