Submission #613371

#	Time	Username	Problem	Language	Result	Execution time	Memory
613371		GusterGoose27	Ruka (COI15_ruka)	C++11	0 / 100	3 ms	468 KiB

ruka

#include <bits/stdc++.h>

using namespace std;

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 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) {
		for (int 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);
	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), 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;
				}
			}
		}
	}
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 35
• Subtask 3: 0 / 56