oj.uz

Submission #27272

# Submission time Handle Problem Language Result Execution time Memory
27272 2017-07-12T06:32:50 Z 구사과(#1145) Ruka (COI15_ruka) C++14
100 / 100
 1786 ms 16136 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

struct jaryo{
	map<int, int> mp;
	int offset = -200000000;
	void update(int dx){
		offset += dx;
	}
	int query(){
		int ret = 0;
		for(int i=-offset; i; i-=i&-i){
			if(mp.find(i) != mp.end()) ret += mp[i];
		}
		return ret;
	}
	void add(int x, int v){
		x -= offset;
		while(x <= 500000000){
			mp[x] += v;
			x += x & -x;
		}
	}
}jx0, jx1, jy0, jy1;

void add(jaryo &j, int s, int e){
	if(s > e) swap(s, e);
	j.add(s, 1);
	j.add(e, -1);
}

void rem(jaryo &j, int s, int e){
	if(s > e) swap(s, e);
	j.add(s, -1);
	j.add(e, 1);
}
char buf[4];
int n, q, x[100005], y[100005];

int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++) scanf("%d %d",&x[i],&y[i]);
	int p = 1, sx = 1, sy = 1;
	for(int i=1; i<=n; i++){
		if(i != 1) add(jx1, sx, sx + x[i]);
		if(i != 1) add(jy1, sy, sy + y[i]);
		sx += x[i];
		sy += y[i];
	}
	sx = sy = 1;
	scanf("%d",&q);
	while(q--){
		scanf("%s", buf);
		if(*buf == 'Q'){
			int ans = jx0.query() + jx1.query() + jy0.query() + jy1.query();
			if(1ll * sx * (sx + x[p]) < 0) ans++;
			if(1ll * sy * (sy + y[p]) < 0) ans++;
			printf("%d\n", ans);
		}
		if(*buf == 'B'){
			if(p == 1) continue;
			add(jx1, sx, sx + x[p]);
			add(jy1, sy, sy + y[p]);
			p--;
			sx -= x[p];
			sy -= y[p];
			rem(jx0, sx, sx + x[p]);
			rem(jy0, sy, sy + y[p]);
		}
		if(*buf == 'F'){
			if(p == n) continue;
			add(jx0, sx, sx + x[p]);
			add(jy0, sy, sy + y[p]);
			sx += x[p];
			sy += y[p];
			p++;
			rem(jx1, sx, sx + x[p]);
			rem(jy1, sy, sy + y[p]);
		}
		if(*buf == 'C'){
			int nx, ny;
			scanf("%d %d",&nx,&ny);
			jx1.update(nx - x[p]);
			jy1.update(ny - y[p]);
			x[p] = nx, y[p] = ny;
		}
	}
}

Compilation message

ruka.cpp: In function 'int main()':
ruka.cpp:44:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
ruka.cpp:45:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%d %d",&x[i],&y[i]);
                                                    ^
ruka.cpp:54:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
                ^
ruka.cpp:56:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", buf);
                   ^
ruka.cpp:85:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&nx,&ny);
                          ^

Subtask #1
9.0 / 9.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2936 KB Output is correct
2 Correct 3 ms 2936 KB Output is correct
3 Correct 3 ms 2936 KB Output is correct
4 Correct 3 ms 2936 KB Output is correct
5 Correct 383 ms 7292 KB Output is correct
6 Correct 346 ms 6500 KB Output is correct
7 Correct 239 ms 4652 KB Output is correct
8 Correct 243 ms 4652 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2936 KB Output is correct
2 Correct 3 ms 2936 KB Output is correct
3 Correct 3 ms 2936 KB Output is correct
4 Correct 3 ms 2936 KB Output is correct
5 Correct 383 ms 7292 KB Output is correct
6 Correct 346 ms 6500 KB Output is correct
7 Correct 239 ms 4652 KB Output is correct
8 Correct 243 ms 4652 KB Output is correct
9 Correct 1469 ms 13760 KB Output is correct
10 Correct 1786 ms 16136 KB Output is correct
11 Correct 1213 ms 12572 KB Output is correct
12 Correct 1446 ms 12044 KB Output is correct