oj.uz

Submission #27438

# Submission time Handle Problem Language Result Execution time Memory
27438 2017-07-12T15:07:03 Z gs14004 Ruka (COI15_ruka) C++14
100 / 100
 1943 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 6 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 6 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 369 ms 7292 KB Output is correct
6 Correct 289 ms 6500 KB Output is correct
7 Correct 249 ms 4652 KB Output is correct
8 Correct 239 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 6 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 369 ms 7292 KB Output is correct
6 Correct 289 ms 6500 KB Output is correct
7 Correct 249 ms 4652 KB Output is correct
8 Correct 239 ms 4652 KB Output is correct
9 Correct 1276 ms 13760 KB Output is correct
10 Correct 1943 ms 16136 KB Output is correct
11 Correct 1363 ms 12572 KB Output is correct
12 Correct 1526 ms 12044 KB Output is correct