oj.uz

답안 #27273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
27273 2017-07-12T06:33:29 Z 까제비(#1140) Ruka (COI15_ruka) C++14
9 / 100
 2000 ms 3836 KB 
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi; typedef pair<ll, int> pli; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 1e5 + 1000, ROOT_N = 400;

pi operator+(const pi &a, const pi &b) { return pi(a.one+b.one, a.two+b.two); }
pi operator-(const pi &a, const pi &b) { return pi(a.one-b.one, a.two-b.two); }
int N, Q; vector<pi> Ps;
pi Sum[MAX_N / ROOT_N];
struct IDX {
	int P; vector<int> val;
	vector<int> Co;
	IDX() {}
	IDX(int n) {
		for(P=1; P<n; P<<=1);
		val = vector<int>(2*P, 0);
	}
	void setting(vector<int> co) {
		sort(ALL(co)); co.erase(unique(ALL(co)), co.end());
		Co = co;
		for(int i=0; i<2*P; i++) val[i] = 0;
	}
	void update(int v, int p, int k) {
		v = lower_bound(ALL(Co), v) - Co.begin() + p;
		if(v >= SZ(Co)) return;
		for(val[v+=P] += k; v>>=1; val[v] = val[v*2] + val[v*2+1]);
	}
	int getSum(int v) {
		int ll = v;
		v = lower_bound(ALL(Co), v) - Co.begin() - 1;
//		printf("%d -> %dth\n", ll, v);
		if(v < 0) return 0;
		int a = 0, b = v, res = 0;
		for(a+=P, b+=P; a<=b; a>>=1, b>>=1) {
			if(a%2==1) res += val[a++];
			if(b%2==0) res += val[b--];
		}
		return res;
	}
};
IDX idx[2][MAX_N / ROOT_N];

void updateG(int i) {
	pi now = pi(0, 0);
	vector<int> co[2]; co[0].push_back(0), co[1].push_back(0);
	for(int j=0, p=i*ROOT_N; p<N && j<ROOT_N; j++, p++) {
		now = now + Ps[p];
		co[0].push_back(now.one);
		co[1].push_back(now.two);
	}
	idx[0][i].setting(co[0]);
	idx[1][i].setting(co[1]);

//	printf("setting well\n");

	now = pi(0, 0);
	for(int j=0, p=i*ROOT_N; p<N && j<ROOT_N; j++, p++) {
		pi past = now;
		now = now + Ps[p];
		idx[0][i].update(min(past.one, now.one), 0, +1);
		idx[0][i].update(max(past.one, now.one), 0, -1);
		idx[1][i].update(min(past.two, now.two), 0, +1);
		idx[1][i].update(max(past.two, now.two), 0, -1);

//		printf("[%d %d] -> [%d %d]\n", past.one, past.two, now.one, now.two);
	}
}
int main() {
	cin >> N;
	pi base = pi(1, 1);
	for(int i=0; i<N; i++) {
		int x, y; scanf("%d%d", &x, &y);
		Ps.push_back(pi(x, y));
		Sum[i / ROOT_N] = Sum[i / ROOT_N] + pi(x, y);
	}
	for(int i=0; i<=(N-1)/ROOT_N; i++) {
		idx[0][i] = idx[1][i] = IDX(ROOT_N);
		updateG(i);
	}
	cin >> Q;
	int cur = 0;
	while(Q--) {
		char s[5]; scanf("%s", s);
		if(s[0] == 'C') {
			int x, y; scanf("%d%d", &x, &y);
			int i = cur / ROOT_N;
			Sum[i] = Sum[i] - Ps[cur];
			Ps[cur] = pi(x, y);
			Sum[i] = Sum[i] + Ps[cur];
			updateG(i);
		} else if(s[0] == 'F') {
			cur = min(N-1, cur+1);
		} else if(s[0] == 'B') {
			cur = max(0, cur-1);
		} else if(s[0] == 'Q') {
			pi sum = base;
			int ans = 0;
			for(int i=0; i<=(N-1)/ROOT_N; i++) {
				ans += idx[0][i].getSum(-sum.one);
				ans += idx[1][i].getSum(-sum.two);
				sum = sum + Sum[i];
			}
			printf("%d\n", ans);
		}else assert(false);
	}


	return 0;
}

/*

struct IDX {
	int P; vector<pi> val;
	IDX() {}
	IDX(int n) {
		for(P=1; P<n; P<<=1);
		val = vector<pi>(2*P);
	}
	void update(int v, pi p) {
		for(val[v+=P] = p; v>>=1; val[v] = val[v*2] + val[v*2+1]);
	}
	pi getSum(int a, int b) {
		pi res = pi(0, 0);
		for(a+=P, b+=P; a<=b; a>>=1, b>>=1) {
			if(a%2==1) res = res + val[a++];
			if(b%2==0) res = res + val[b--];
		}
		return res;
	}
};
*/

Compilation message

ruka.cpp: In member function 'int IDX::getSum(int)':
ruka.cpp:41:7: warning: unused variable 'll' [-Wunused-variable]
   int ll = v;
       ^
ruka.cpp: In function 'int main()':
ruka.cpp:84:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
                                  ^
ruka.cpp:95:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char s[5]; scanf("%s", s);
                            ^
ruka.cpp:97:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x, y; scanf("%d%d", &x, &y);
                                   ^

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2056 KB Output is correct
2 Correct 3 ms 2056 KB Output is correct
3 Correct 109 ms 2056 KB Output is correct
4 Correct 79 ms 2056 KB Output is correct

Subtask #2
0 / 35.0

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

Subtask #3
0 / 56.0

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