Submission #27303

#	Time	Username	Problem	Language	Result	Execution time	Memory
27303		kajebiii	Ruka (COI15_ruka)	C++14	100 / 100	513 ms	19052 KiB

ruka

#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 (stderr)

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 / 9
• Subtask 2: 35 / 35
• Subtask 3: 56 / 56