oj.uz

Submission #27408

# Submission time Handle Problem Language Result Execution time Memory
27408 2017-07-12T12:22:30 Z kdh9949 Ruka (COI15_ruka) C++14
100 / 100
 1346 ms 17852 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2940 KB Output is correct
2 Correct 3 ms 2940 KB Output is correct
3 Correct 6 ms 2940 KB Output is correct
4 Correct 3 ms 2940 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2940 KB Output is correct
2 Correct 3 ms 2940 KB Output is correct
3 Correct 6 ms 2940 KB Output is correct
4 Correct 3 ms 2940 KB Output is correct
5 Correct 429 ms 8512 KB Output is correct
6 Correct 366 ms 8164 KB Output is correct
7 Correct 399 ms 6020 KB Output is correct
8 Correct 379 ms 6012 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2940 KB Output is correct
2 Correct 3 ms 2940 KB Output is correct
3 Correct 6 ms 2940 KB Output is correct
4 Correct 3 ms 2940 KB Output is correct
5 Correct 429 ms 8512 KB Output is correct
6 Correct 366 ms 8164 KB Output is correct
7 Correct 399 ms 6020 KB Output is correct
8 Correct 379 ms 6012 KB Output is correct
9 Correct 1179 ms 15472 KB Output is correct
10 Correct 1346 ms 17852 KB Output is correct
11 Correct 1066 ms 14380 KB Output is correct
12 Correct 1103 ms 13128 KB Output is correct