| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 614197 | GusterGoose27 | Ruka (COI15_ruka) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 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), 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;
}
}
}
}
}