oj.uz

Submission #614201

# Submission time Handle Problem Language Result Execution time Memory
614201 2022-07-30T21:46:55 Z GusterGoose27 Ruka (COI15_ruka) C++11
44 / 100
 2000 ms 6048 KB 
#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;
				}
			}
		}
	}
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 29 ms 476 KB Output is correct
4 Correct 17 ms 496 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 29 ms 476 KB Output is correct
4 Correct 17 ms 496 KB Output is correct
5 Correct 1349 ms 5516 KB Output is correct
6 Correct 1476 ms 2904 KB Output is correct
7 Correct 1918 ms 5672 KB Output is correct
8 Correct 1992 ms 5872 KB Output is correct

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 29 ms 476 KB Output is correct
4 Correct 17 ms 496 KB Output is correct
5 Correct 1349 ms 5516 KB Output is correct
6 Correct 1476 ms 2904 KB Output is correct
7 Correct 1918 ms 5672 KB Output is correct
8 Correct 1992 ms 5872 KB Output is correct
9 Execution timed out 2067 ms 6048 KB Time limit exceeded
10 Halted 0 ms 0 KB -