Submission #27288

#	Time	Username	Problem	Language	Result	Execution time	Memory
27288		suhgyuho_william	Ruka (COI15_ruka)	C++14	9 / 100	2000 ms	11948 KiB

ruka

#include <bits/stdc++.h>

#define lld long long
#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define next nextt
#define Inf 1000000000
#define Linf 1000000000000000000LL
#define Mod 1000000007

using namespace std;

int N,M,where,sqrtn,ans,bsize;
int nx[100002],ny[100002];
int sx[100002],ex[100002],sy[100002],ey[100002];
int addx[100002],addy[100002];
struct data{
	int x,y;
}a[100002];
vector<pii> memox[100002],memoy[100002];

void f(int num){
	if(a[num].x > 0){
		sx[num] = -a[num].x-nx[num];
		ex[num] = -nx[num];
	}else if(a[num].x < 0){
		sx[num] = -nx[num];
		ex[num] = -a[num].x-nx[num];
	}else{
		sx[num] = 1; ex[num] = 0;
	}
	if(a[num].y > 0){
		sy[num] = -a[num].y-ny[num];
		ey[num] = -ny[num];
	}else if(a[num].y < 0){
		sy[num] = -ny[num];
		ey[num] = -a[num].y-ny[num];
	}else{
		sy[num] = 1; ey[num] = 0;
	}
}

void setting(int num){
	int s,e;
	s = max(1,num*bsize);
	e = min(N,(num+1)*bsize-1);

	vector<pii> X,Y;
	for(int i=s; i<=e; i++){
		nx[i] += addx[num]; ny[i] += addy[num];
		f(i);
		if(sx[i] <= ex[i]){
			X.pb({sx[i],1});
			X.pb({ex[i],-1});
		}
		if(sy[i] <= ey[i]){
			Y.pb({sy[i],1});
			Y.pb({ey[i],-1});
		}
	}
	addx[num] = addy[num] = 0;
	memox[num].clear(); memoy[num].clear();
	sort(X.begin(),X.end()); sort(Y.begin(),Y.end());
	for(auto &i : X){
		if(memox[num].empty()){
			memox[num].pb(i);
		}else if(memox[num].back().first == i.first){
			memox[num].back().second += i.second;
		}else{
			memox[num].pb(i);
			memox[num].back().second += memox[num][memox[num].size()-2].second;
		}
	}
	for(auto &i : Y){
		if(memoy[num].empty()){
			memoy[num].pb(i);
		}else if(memoy[num].back().first == i.first){
			memoy[num].back().second += i.second;
		}else{
			memoy[num].pb(i);
			memoy[num].back().second += memoy[num][memoy[num].size()-2].second;
		}
	}
}
int calc(int num){
	int sum = 0;
	if(memox[num].size() != 0){
		if(addx[num] >= memox[num][0].first){
			int l,r,t;
			l = 0; r = memox[num].size()-1;
			while(l <= r){
				int m = (l+r)>>1;
				if(addx[num] >= memox[num][m].first){
					t = m;
					l = m+1;
				}else r = m-1;
			}
			sum += memox[num][t].second;
		}
	}
	if(memoy[num].size() != 0){
		if(addy[num] >= memoy[num][0].first){
			int l,r,t;
			l = 0; r = memoy[num].size()-1;
			while(l <= r){
				int m = (l+r)>>1;
				if(addy[num] >= memoy[num][m].first){
					t = m;
					l = m+1;
				}else r = m-1;
			}
			sum += memoy[num][t].second;
		}
	}
	return sum;
}

int main(){
	scanf("%d",&N);
	for(int i=1; i<=N; i++) scanf("%d %d",&a[i].x,&a[i].y);
	scanf("%d",&M);

	bsize = sqrt(N);
	nx[1] = ny[1] = 1;
	for(int i=1; i<=N; i++){
		nx[i+1] = nx[i]+a[i].x;
		ny[i+1] = ny[i]+a[i].y;
	}
	for(int i=0; i<=N/bsize; i++){
		setting(i);
		ans += calc(i);
	}
	where = 1;
	for(int i=1; i<=M; i++){
		int x,y;
		char s[3];
		scanf("%s",s);
		if(s[0] == 'B') where = max(1,where-1);
		else if(s[0] == 'F') where = min(where+1,N);
		else if(s[0] == 'Q'){
			printf("%d\n",ans);
		}else{
			scanf("%d %d",&x,&y);
			int s,e;
			s = max(where+1,(where/bsize)*bsize);
			e = min(N,(where/bsize+1)*bsize-1);
			for(int j=where/bsize+1; j<=N/bsize; j++){
				ans -= calc(j);
				addx[j] += (x-a[where].x); addy[j] += (y-a[where].y);
				ans += calc(j);
			}
			ans -= calc(where/bsize);
			for(int j=s; j<=e; j++){
				nx[j] += (x-a[where].x); ny[j] += (y-a[where].y);
			}
			a[where].x = x; a[where].y = y;
			setting(where/bsize);
			ans += calc(where/bsize);
		}
	}

	return 0;
}

Compilation message (stderr)

ruka.cpp: In function 'int main()':
ruka.cpp:120:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
                ^
ruka.cpp:121:56: 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",&a[i].x,&a[i].y);
                                                        ^
ruka.cpp:122:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&M);
                ^
ruka.cpp:138:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s);
                ^
ruka.cpp:144:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&x,&y);
                        ^
ruka.cpp: In function 'int calc(int)':
ruka.cpp:113:23: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
    sum += memoy[num][t].second;
                       ^
ruka.cpp:99:23: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
    sum += memox[num][t].second;
                       ^

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