Submission #369249

#	Time	Username	Problem	Language	Result	Execution time	Memory
369249		YJU	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1532 ms	211792 KiB

rainbow

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e5+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
 
vector<ll> seg[4][4*N];
 
void ins(ll sid,ll id,ll l,ll r,ll tox,ll toy){
	seg[sid][id].pb(toy);
	if(l==r-1)return ;
	ll mid=(l+r)>>1;
	if(tox<mid){
		ins(sid,id*2,l,mid,tox,toy);
	}else{
		ins(sid,id*2+1,mid,r,tox,toy);
	}
}
 
ll query(ll sid,ll id,ll l,ll r,ll fl,ll fr,ll bl,ll br){
	if(l>=fl&&r<=fr){
		return -1*(lwb(seg[sid][id].begin(),seg[sid][id].end(),br)-lwb(seg[sid][id].begin(),seg[sid][id].end(),bl));
	}
	if(l>=fr||r<=fl)return 0;
	ll mid=(l+r)>>1;
	return query(sid,id*2,l,mid,fl,fr,bl,br)+query(sid,id*2+1,mid,r,fl,fr,bl,br);
}
 
//for [ar,br] [ac,bc]
//sid=0 V : [ar,br] [ac,bc]
//sid=1 VE : [ar,br) [ac,bc]
//sid=2 HE : [ar,br] [ac,bc)
//sid=3 F : [ar,br) [ac,bc)
 
int mir,mxr,mic,mxc;
 
void init(int R,int C,int sr,int sc,int M,char *S){
	vector<pll> v[4];
	mic=mxc=sc;
	mir=mxr=sr;
	for(int i=0;i<=M;i++){
		mic=min(mic,sc);mxc=max(mxc,sc);
		mir=min(mir,sr);mxr=max(mxr,sr);
		v[0].pb(mp(sr,sc));
		v[1].pb(mp(sr,sc));v[1].pb(mp(sr-1,sc));
		v[2].pb(mp(sr,sc));v[2].pb(mp(sr,sc-1));
		v[3].pb(mp(sr,sc));v[3].pb(mp(sr-1,sc));v[3].pb(mp(sr,sc-1));v[3].pb(mp(sr-1,sc-1));
		//
		if(i==M)break;
		if(S[i]=='N')--sr;
		if(S[i]=='S')++sr;
		if(S[i]=='W')--sc;
		if(S[i]=='E')++sc;
	}
	//unique
	for(int i=0;i<4;i++)sort(v[i].begin(),v[i].end(),[](pll A,pll B){
		if(A.Y!=B.Y)return A.Y<B.Y;
		return A.X<B.X;
	}),v[i].erase(unique(v[i].begin(),v[i].end()),v[i].end());
	//
	for(int sid=0;sid<4;sid++){
		for(auto i:v[sid]){
			ins(sid,1,0,N,i.X,i.Y);
		}
		//REP(i,4*N)sort(seg[sid][i].begin(),seg[sid][i].end());
	}
}
 
int colour(int ar,int ac,int br,int bc){
	ll ans=1;
	ans+=query(0,1,0,N,ar,br+1,ac,bc+1);
	ans-=query(1,1,0,N,ar,br,ac,bc+1);
	ans-=query(2,1,0,N,ar,br+1,ac,bc);
	ans+=query(3,1,0,N,ar,br,ac,bc);
	ans+=(mxc<bc&&mic>ac&&mxr<br&&mir>ar?1:0);
	return ans;
}
/*
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	init(6,4,3,3,9,"NWESSWEWS");
	cout<<colour(2,3,2,3)<<"\n";
	cout<<colour(3,2,4,4)<<"\n";
	cout<<colour(5,3,6,4)<<"\n";
	cout<<colour(1,2,5,3)<<"\n";
	return 0;
}
//*/

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