oj.uz

답안 #27301

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
27301 2017-07-12T07:25:31 Z 윤교준(#1144) Ruka (COI15_ruka) C++11
9 / 100
 2000 ms 8348 KB 
#include <bits/stdc++.h>
#define pb push_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[(sz(V)-2)])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define rb(x) ((x)&(-(x)))
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define MOD (1000000007)
#define MAXN (100005)
#define SQN (333)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX = 131072;
struct SEG {
	int d[MX*2];
	void upd(int x, int r) { for(x += MX, d[x] = r, x /= 2; x; x /= 2) d[x] = d[x*2] + d[x*2+1]; }
	int get(int s, int e) {
		int r = 0; for(s += MX, e += MX; s <= e; s /= 2, e /= 2) {
			if(s&1) r += d[s++]; if(~e&1) r += d[e--];
		} return r;
	}
	int get(int x) { return get(x, x); }
};
struct Node {
	int VX[SQN*2+5], S[SQN*2+5];
	int N, cx;
	void init() {}
	void mv(int dx) { cx += dx; }
	void make(vector<pii>& V) {
		N = cx = 0; if(V.empty()) return;
		vector<pii> Q;
		for(pii& v : V) {
			if(v.first > v.second) swap(v.first, v.second);
			v.second++;
			Q.pb({v.first, 1}); Q.pb({v.second, -1});
		}
		sorv(Q);
		VX[0] = S[0] = 0;
		for(int i = 0, j; i < sz(Q); i = j) {
			for(j = i+1; j < sz(Q) && Q[i].first == Q[j].first; j++);
			N++; S[N] = S[N-1]; VX[N] = Q[i].first;
			for(int k = i; k < j; k++) S[N] += Q[k].second;
		}
	}
	int get(int X = 0) {
		if(!N) return 0;
		X -= cx;
		if(X < VX[1] || VX[N] < X) return 0;
		int idx = (int)(lower_bound(VX+1, VX+N+1, X) - VX);
		if(VX[idx] != X) idx--;
		return S[idx];
	}
	void debug() {
		printf("N = %d, cx = %d\n", N, cx);
		for(int i = 1; i <= N; i++) printf("VX[%d] = %d, S[%d] = %d\n", i, VX[i], i, S[i]);
		puts("\n");
	}
};

SEG segX, segY;
Node nodeX[SQN], nodeY[SQN];
int X[MAXN], Y[MAXN];
int N, M, pt = 1;

void initNode(int i) {
	int s = i*SQN + 1, e = min(N, (i+1)*SQN);
	vector<pii> V;
	for(int l = s; l <= e; l++) V.pb({segX.get(1, l), segX.get(1, l+1)});
	nodeX[i].make(V); clv(V);
	for(int l = s; l <= e; l++) V.pb({segY.get(1, l), segY.get(1, l+1)});
	nodeY[i].make(V);
}
void initNode() {
	for(int i = 0; i < SQN; i++) {
		if(N <= i*SQN) break;
		initNode(i);
	}
}
void f(int dx, int dy) {
	for(int i = 0; i < SQN; i++) {
		int s = i*SQN + 1, e = min(N, (i+1)*SQN);
		if(N < s) break;
		if(e < pt) continue;
		if(s <= pt && pt <= e) initNode(i);
		else { nodeX[i].mv(dx); nodeY[i].mv(dy); }
	}
}
int getAns() {
	int ret = 0;
	for(int i = 0; i < SQN; i++) {
		if(N <= i*SQN) break;
		ret += nodeX[i].get() + nodeY[i].get();
	}
	return ret;
}
int main() {
	scanf("%d", &N);
	X[1] = Y[1] = 1; for(int i = 1; i <= N; i++) {
		int dx, dy; scanf("%d%d", &dx, &dy);
		X[i+1] = X[i] + dx; Y[i+1] = Y[i] + dy;
	}
	for(int i = 1; i <= N+1; i++) {
		segX.upd(i, X[i] - X[i-1]);
		segY.upd(i, Y[i] - Y[i-1]);
	}
	initNode();
	for(scanf("%d", &M); M--;) {
		char c; scanf(" %c", &c);
		if('F' == c) pt = min(pt+1, N);
		else if('B' == c) pt = max(1, pt-1);
		else if('Q' == c) printf("%d\n", getAns());
		else {
			int dx, dy; scanf("%d%d", &dx, &dy);
			int rx = dx - segX.get(pt+1), ry = dy - segY.get(pt+1);
			segX.upd(pt+1, dx); segY.upd(pt+1, dy);
			f(rx, ry);
		}
	}
	return 0;
}

Compilation message

ruka.cpp: In function 'int main()':
ruka.cpp:105:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
ruka.cpp:107:38: 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);
                                      ^
ruka.cpp:115: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:116: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:121: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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8348 KB Output is correct
2 Correct 3 ms 8348 KB Output is correct
3 Correct 113 ms 8348 KB Output is correct
4 Correct 86 ms 8348 KB Output is correct

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8348 KB Output is correct
2 Correct 3 ms 8348 KB Output is correct
3 Correct 113 ms 8348 KB Output is correct
4 Correct 86 ms 8348 KB Output is correct
5 Execution timed out 2000 ms 8348 KB Execution timed out
6 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8348 KB Output is correct
2 Correct 3 ms 8348 KB Output is correct
3 Correct 113 ms 8348 KB Output is correct
4 Correct 86 ms 8348 KB Output is correct
5 Execution timed out 2000 ms 8348 KB Execution timed out
6 Halted 0 ms 0 KB -