oj.uz

Submission #614218

# Submission time Handle Problem Language Result Execution time Memory
614218 2022-07-30T22:07:25 Z GusterGoose27 Ruka (COI15_ruka) C++11
44 / 100
 2000 ms 2588 KB 
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 1e5;
int n, q;
const int BSIZE = 200;
const int MAXBLOCKS = 501;
int num_blocks;
int numsx[MAXN];
int numsy[MAXN];
pii vecs[MAXN];
int xlz[MAXN];
int ylz[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);
			}
		}
		shiftx = 0;
		shifty = 0;
		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(NULL);
	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;
			int cxlz = 0;
			int cylz = 0;
			for (int j = 0; j < num_blocks; j++) {
				cxlz += xlz[j];
				cylz += ylz[j];
				xlz[j] = ylz[j] = 0;
				blocks[j].shiftx += cxlz;
				blocks[j].shifty += cylz;
				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+cxlz+xlz[j+1];
					int y2 = numsy[blocks[j+1].lp]+blocks[j+1].shifty+cylz+ylz[j+1];
					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);
			int j = pos/BSIZE;
			blocks[j].upd(pos+1, blocks[j].rp, xsh, ysh);
			if (j < num_blocks-1) {
				xlz[j+1] += xsh;
				ylz[j+1] += 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 340 KB Output is correct
3 Correct 16 ms 440 KB Output is correct
4 Correct 10 ms 440 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 340 KB Output is correct
3 Correct 16 ms 440 KB Output is correct
4 Correct 10 ms 440 KB Output is correct
5 Correct 1083 ms 2228 KB Output is correct
6 Correct 1016 ms 1248 KB Output is correct
7 Correct 1686 ms 2372 KB Output is correct
8 Correct 1573 ms 2584 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 340 KB Output is correct
3 Correct 16 ms 440 KB Output is correct
4 Correct 10 ms 440 KB Output is correct
5 Correct 1083 ms 2228 KB Output is correct
6 Correct 1016 ms 1248 KB Output is correct
7 Correct 1686 ms 2372 KB Output is correct
8 Correct 1573 ms 2584 KB Output is correct
9 Execution timed out 2073 ms 2588 KB Time limit exceeded
10 Halted 0 ms 0 KB -