Submission #27408

#	Time	Username	Problem	Language	Result	Execution time	Memory
27408		kdh9949	Ruka (COI15_ruka)	C++14	100 / 100	1346 ms	17852 KiB

ruka

#include <bits/stdc++.h>
using namespace std;

int n, q, l, tx[2], dx[100010][2], off[2];

const int B = 150000010;
struct BIT{
	unordered_map<int, int> dat;
	void upd(int x, int v){ for(x += B; x <= 2 * B; x += x & -x) dat[x] += v; }
	int get(int x){ int ret = 0; for(x += B; x; x -= x & -x) ret += dat[x]; return ret; }
} U[2], D[2];

void ch(BIT &B, int t, int off, int v){
	int s, e; tie(s, e) = minmax(tx[t], tx[t] + dx[l][t]);
	B.upd(s + off, v);
	B.upd(e + off, -v);
}

void ap(int t){
	ch(D[t], t, off[t], -1);
	ch(U[t], t, 0, 1);
	tx[t] += dx[l][t];
}

void dui(int t){
	tx[t] -= dx[l][t];
	ch(U[t], t, 0, -1);
	ch(D[t], t, off[t], 1);
}

void upd(int t, int v){
	ch(D[t], t, off[t], -1);
	dx[l][t] += v;
	off[t] -= v;
	ch(D[t], t, off[t], 1);
}

int get(int t){
	return U[t].get(0) + D[t].get(off[t]);
}

int main(){
	scanf("%d", &n);
	tx[0] = tx[1] = 1;
	for(int i = 1; i <= n; i++){
		scanf("%d%d", dx[i], dx[i] + 1);
		for(int t = 0; t < 2; t++){
			int nx = tx[t] + dx[i][t];
			D[t].upd(min(tx[t], nx), 1);
			D[t].upd(max(tx[t], nx), -1);
			tx[t] = nx;
		}
	}
	l = 1;
	tx[0] = tx[1] = 1;
	scanf("%d", &q);
	for(char t; q--; ){
		scanf(" %c", &t);
		if(t == 'F' && l < n){ ap(0); ap(1); l++; }
		else if(t == 'B' && l > 1){ l--; dui(0); dui(1); }
		else if(t == 'C'){
			int x[2]; scanf("%d%d", x, x + 1);
			upd(0, x[0] - dx[l][0]); upd(1, x[1] - dx[l][1]);
		}
		else if(t == 'Q'){
			printf("%d\n", get(0) + get(1));
		}
	}
}

Compilation message (stderr)

ruka.cpp: In function 'int main()':
ruka.cpp:43:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
ruka.cpp:46:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", dx[i], dx[i] + 1);
                                  ^
ruka.cpp:56:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
                 ^
ruka.cpp:58:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &t);
                   ^
ruka.cpp:62:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x[2]; scanf("%d%d", x, x + 1);
                                     ^

• Subtask 1: 9 / 9
• Subtask 2: 35 / 35
• Subtask 3: 56 / 56