Submission #105420

#	Time	Username	Problem	Language	Result	Execution time	Memory
105420		puyu_liao	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1558 ms	91144 KiB

rainbow

#include<bits/stdc++.h>
#include<stdint.h>
using namespace std;
#define IOS {cin.tie(0);ios_base::sync_with_stdio(false);}
#define N 200005
#define lowbit(x) (x&-x)
#include"rainbow.h"
struct dbit{
	vector<int> v[N];
	int n,m;
	void init(int _n,int _m){
		n = _n,m = _m;
		for(int i=1;i<=n;i++) v[i].clear();
	}
	void ins(int x,int y){
		for(;x<=n;x+=lowbit(x)) v[x].push_back(y);
	}
	void preprocess(){
		for(int i=1;i<=n;i++){
			sort(v[i].begin(),v[i].end());
		}
	}
	int qur(int x,int y,int xx,int yy){
		if(x > xx || y > yy) return 0;
		int r = 0;
		for(;x;x-=lowbit(x)) r -= (int)(upper_bound(v[x].begin(),v[x].end(),yy) - lower_bound(v[x].begin(),v[x].end(),y));
		for(;xx;xx-=lowbit(xx)) r += (int)(upper_bound(v[xx].begin(),v[xx].end(),yy) - lower_bound(v[xx].begin(),v[xx].end(),y));
		return r;
	}
}bv,be1,be2,bf;
vector<pair<int,int> > v;
set<pair<int,int> > sv,se1,se2,sf;
int xmn,xmx,ymn,ymx;
 
void put(int sr,int sc){
	sv.insert({sr,sc});
	sv.insert({sr+1,sc});
	sv.insert({sr,sc+1});
	sv.insert({sr+1,sc+1});
	se1.insert({sr,sc}); 
	se1.insert({sr,sc+1}); 
	se2.insert({sr,sc}); 
	se2.insert({sr+1,sc}); 
	sf.insert({sr,sc});
}
 
void init(int R,int C,int sr,int sc,int M,char* S){
	bv.init(R+2,C+2);
	be1.init(R+2,C+2); //vert
	be2.init(R+2,C+2); //hori
	bf.init(R+2,C+2);
	sv.clear();
	se1.clear();
	se2.clear();
	sf.clear();
	put(sr,sc);
	xmn = xmx = sr, ymn = ymx = sc;
	for(int j=0;j<M;j++){
		char &i = S[j];
		if(i == 'N') sr--;
		else if(i == 'E') sc++;
		else if(i == 'W') sc--;
		else if(i == 'S') sr++;
		v.push_back({sr,sc});
		xmx = max(xmx,sr);
		xmn = min(xmn,sr);
		ymx = max(ymx,sc);
		ymn = min(ymn,sc);
		put(sr,sc);
	}
	for(auto i : sv) bv.ins(i.first,i.second);
	for(auto i : se1) be1.ins(i.first,i.second);
	for(auto i : se2) be2.ins(i.first,i.second);
	for(auto i : sf) bf.ins(i.first,i.second);
	bv.preprocess();
	be1.preprocess();
	be2.preprocess();
	bf.preprocess();
}
 
int colour(int ar,int ac,int br,int bc){
	int v = (br-ar+bc-ac+2)*2 + bv.qur(ar,ac+1,br,bc);
	int e = (br-ar+bc-ac+2)*2 + be1.qur(ar-1,ac+1,br,bc) + be2.qur(ar,ac,br,bc);
	int f = bf.qur(ar-1,ac,br,bc);
	//cout << v << ' ' << e << ' ' << f << '\n';
	return e-v-f + 1 + (ar < xmn && ac < ymn && br > xmx && bc > ymx);
}

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26