oj.uz

Submission #27303

# Submission time Handle Problem Language Result Execution time Memory
27303 2017-07-12T07:32:04 Z kajebiii Ruka (COI15_ruka) C++14
100 / 100
 513 ms 19052 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, BASE = 5e7 + 100;
 
int N, Q, Nr[2][MAX_N];
struct NODE {
	int l, r, v;
	NODE *lp, *rp;
	NODE(int a, int b) : l(a), r(b), v(0), lp(NULL), rp(NULL) {}
	void update(int a, int b, int k) {
		if(r < a || b < l) return;
		if(a <= l && r <= b) {
//			printf("[%d %d] %d %d | %d\n", l, r, a, b, k);
			v += k;
			return;
		}
		int m = (l+r) >> 1;
		if(!lp) lp = new NODE(l  , m); lp -> update(a, b, k);
		if(!rp) rp = new NODE(m+1, r); rp -> update(a, b, k);
	}
	int getSum(int i) {
		if(r < i || i < l) return 0;
		int m = (l+r) >> 1;
		int res = v;
		if(lp) res += lp -> getSum(i);
		if(rp) res += rp -> getSum(i);
		return res;
	}
}*root[2];
void update(int t, int a, int b, int k) {
	if(a > b) swap(a, b);
	root[t] -> update(a, b, k);
}
int getSum(int t, int v) {
	return root[t] -> getSum(v);
}
int main() {
	cin >> N;
	for(int i=0; i<N; i++) {
		int x, y; scanf("%d%d", &x, &y);
		Nr[0][i] = x; Nr[1][i] = y;
	}
	root[0] = new NODE(-BASE, +BASE);
	root[1] = new NODE(-BASE, +BASE);
 
	int now[2] = {1, 1};
	for(int i=0; i<N; i++) {
		for(int k=0; k<2; k++) {
			int next = now[k] + Nr[k][i];
			update(k, now[k], next, 1);
			now[k] = next;
		}
	}
 
	cin >> Q;
	int cur = 0, cnt = 0;
 
	now[0] = now[1] = 1;
	int ori[2] = {0, 0};
	while(Q--) {
		char s[5]; scanf("%s", s);
		if(s[0] == 'C') {
			int nr[2]; scanf("%d%d", &nr[0], &nr[1]);
			for(int k=0; k<2; k++) {
				update(k, now[k] + ori[k], now[k] + ori[k] + Nr[k][cur], -1);
				ori[k] += Nr[k][cur] - nr[k];
				Nr[k][cur] = nr[k];
				update(k, now[k] + ori[k], now[k] + ori[k] + Nr[k][cur], +1);
			}
		} else if(s[0] == 'F') {
			if(cur == N-1) continue;
			for(int k=0; k<2; k++) {
				if( (now[k] < 0) ^ (now[k] + Nr[k][cur]) < 0 ) cnt++;
				update(k, now[k] + ori[k], now[k] + ori[k] + Nr[k][cur], -1);
				now[k] += Nr[k][cur];
			}
			cur = min(N-1, cur+1);
		} else if(s[0] == 'B') {
			if(cur == 0) continue;
			for(int k=0; k<2; k++) {
				if((now[k] < 0) ^ (now[k] - Nr[k][cur-1]) < 0) cnt--;
				update(k, now[k] + ori[k] - Nr[k][cur-1], now[k] + ori[k], +1);
				now[k] -= Nr[k][cur-1];
			}
			cur = max(0, cur-1);
		} else if(s[0] == 'Q') {
			printf("%d\n", cnt + getSum(0, ori[0]) + getSum(1, ori[1]));
		}else assert(false);
	}
 
 
	return 0;
}

Compilation message

ruka.cpp: In member function 'int NODE::getSum(int)':
ruka.cpp:36:7: warning: unused variable 'm' [-Wunused-variable]
   int m = (l+r) >> 1;
       ^
ruka.cpp: In function 'int main()':
ruka.cpp:86:46: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
     if( (now[k] < 0) ^ (now[k] + Nr[k][cur]) < 0 ) cnt++;
                                              ^
ruka.cpp:94:47: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
     if((now[k] < 0) ^ (now[k] - Nr[k][cur-1]) < 0) cnt--;
                                               ^
ruka.cpp:53: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:74: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:76:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int nr[2]; scanf("%d%d", &nr[0], &nr[1]);
                                            ^

Subtask #1
9.0 / 9.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3080 KB Output is correct
2 Correct 0 ms 2948 KB Output is correct
3 Correct 3 ms 3080 KB Output is correct
4 Correct 0 ms 3080 KB Output is correct
5 Correct 169 ms 6644 KB Output is correct
6 Correct 156 ms 9680 KB Output is correct
7 Correct 169 ms 3212 KB Output is correct
8 Correct 173 ms 3212 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3080 KB Output is correct
2 Correct 0 ms 2948 KB Output is correct
3 Correct 3 ms 3080 KB Output is correct
4 Correct 0 ms 3080 KB Output is correct
5 Correct 169 ms 6644 KB Output is correct
6 Correct 156 ms 9680 KB Output is correct
7 Correct 169 ms 3212 KB Output is correct
8 Correct 173 ms 3212 KB Output is correct
9 Correct 479 ms 17996 KB Output is correct
10 Correct 513 ms 19052 KB Output is correct
11 Correct 456 ms 11264 KB Output is correct
12 Correct 503 ms 14036 KB Output is correct