oj.uz

Submission #27422

# Submission time Handle Problem Language Result Execution time Memory
27422 2017-07-12T13:07:59 Z youngyojun Ruka (COI15_ruka) C++11
100 / 100
 586 ms 23644 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4636 KB Output is correct
2 Correct 0 ms 4636 KB Output is correct
3 Correct 3 ms 4636 KB Output is correct
4 Correct 3 ms 4504 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4636 KB Output is correct
2 Correct 0 ms 4636 KB Output is correct
3 Correct 3 ms 4636 KB Output is correct
4 Correct 3 ms 4504 KB Output is correct
5 Correct 163 ms 10840 KB Output is correct
6 Correct 169 ms 10708 KB Output is correct
7 Correct 153 ms 6748 KB Output is correct
8 Correct 159 ms 6880 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4636 KB Output is correct
2 Correct 0 ms 4636 KB Output is correct
3 Correct 3 ms 4636 KB Output is correct
4 Correct 3 ms 4504 KB Output is correct
5 Correct 163 ms 10840 KB Output is correct
6 Correct 169 ms 10708 KB Output is correct
7 Correct 153 ms 6748 KB Output is correct
8 Correct 159 ms 6880 KB Output is correct
9 Correct 579 ms 20608 KB Output is correct
10 Correct 586 ms 23644 KB Output is correct
11 Correct 436 ms 18364 KB Output is correct
12 Correct 516 ms 17572 KB Output is correct