Submission #27422

#	Time	Username	Problem	Language	Result	Execution time	Memory
27422		youngyojun	Ruka (COI15_ruka)	C++11	100 / 100	586 ms	23644 KiB

ruka

#include <bits/stdc++.h>
#define MAXX (255000000)
#define MAXN (100005)
using namespace std;
typedef pair<int, int> pii;
struct SEG {
	SEG() : l(NULL), r(NULL), d(0) {}
	SEG *l, *r;
	int d;
	void upd(int x, int R, int s = -MAXX, int e = MAXX) {
		if(x < s || e < x) return;
		d += R; if(s == e) return;
		int m = (s+e)>>1;
		if(x <= m) {
			if(NULL == l) l = new SEG();
			l -> upd(x, R, s, m);
		} else {
			if(NULL == r) r = new SEG();
			r -> upd(x, R, m+1, e);
		}
	}
	int get(int p, int q, int s = -MAXX, int e = MAXX) {
		if(q < p || q < s || e < p) return 0;
		if(p <= s && e <= q) return d;
		int m = (s+e)>>1;
		return (l ? l -> get(p, q, s, m) : 0) + (r ? r -> get(p, q, m+1, e) : 0);
	}
};
struct Node {
	Node() : pt(1), px(0) {}
	SEG upseg, downseg;
	pii L[MAXN];
	int N, pt, px;
	void updseg(SEG& seg, pii l, int a, int b) {
		if(l.first > l.second) swap(l.first, l.second);
		seg.upd(l.first, a); seg.upd(l.second+1, b);
	}
	void init(int _N, int X[]) {
		N = _N; L[1] = {1, X[1]};
		for(int i = 2; i <= N; i++) L[i] = {X[i-1], X[i]};
		for(int i = 1; i <= N; i++) updseg(downseg, L[i], 1, -1);
	}
	void upf() {
		if(1 == pt) return;
		pt--;
		updseg(upseg, L[pt], -1, 1);
		L[pt].first += px;
		L[pt].second += px;
		updseg(downseg, L[pt], 1, -1);
	}
	void downf() {
		if(N == pt) return;
		updseg(downseg, L[pt], -1, 1);
		L[pt].first -= px;
		L[pt].second -= px;
		updseg(upseg, L[pt], 1, -1);
		pt++;
	}
	void mvf(int dx) {
		int dl = L[pt].first - L[pt].second + dx;
		updseg(downseg, L[pt], -1, 1);
		L[pt].second = L[pt].first + dx;
		L[pt].first -= dl; L[pt].second -= dl;
		updseg(downseg, L[pt], 1, -1);
		px -= dl;
	}
	int getAns() { return upseg.get(-MAXX, 0) + downseg.get(-MAXX, px); }
};

Node nX, nY;
int X[MAXN], Y[MAXN];
int N, M;

void f(int d[]) { d[0] = 1; for(int i = 1; i <= N; i++) d[i] += d[i-1]; }
int main() {
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) scanf("%d%d", &X[i], &Y[i]);
	f(X); f(Y); nX.init(N, X); nY.init(N, Y);
	for(scanf("%d", &M); M--;) {
		char c; scanf(" %c", &c);
		if('Q' == c) printf("%d\n", nX.getAns() + nY.getAns());
		else if('B' == c) { nX.upf(); nY.upf(); }
		else if('F' == c) { nX.downf(); nY.downf(); }
		else {
			int dx, dy; scanf("%d%d", &dx, &dy);
			nX.mvf(dx); nY.mvf(dy);
		}
	}
	return 0;
}

Compilation message (stderr)

ruka.cpp: In function 'int main()':
ruka.cpp:76:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
ruka.cpp:77:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= N; i++) scanf("%d%d", &X[i], &Y[i]);
                                                         ^
ruka.cpp:79:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(scanf("%d", &M); M--;) {
                     ^
ruka.cpp:80:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char c; scanf(" %c", &c);
                           ^
ruka.cpp:85:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int dx, dy; scanf("%d%d", &dx, &dy);
                                       ^

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