제출 #930941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930941		amirhoseinfar1385	무지개나라 (APIO17_rainbow)	C++17	100 / 100	782 ms	404816 KiB

rainbow

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int kaf=(1<<18);

struct segment{
	vector<int>all[maxn];
	void add(int r,int c){
		all[r].push_back(c);
	}	
	struct node{
		int lc,rc,sum;
		node(){
			lc=rc=sum=0;
		}
	};
	node seg[(1<<19)*15];
	int root[maxn],rt=0,nx=1;
	void calc(int i){
		seg[i].sum=seg[seg[i].lc].sum+seg[seg[i].rc].sum;
	}
	int ins(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return i;
		}
		int now=nx;
		seg[nx]=seg[i];
		nx++;
		if(l>=tl&&r<=tr){
			seg[nx-1].sum+=w;
			return nx-1;
		}
		int m=(l+r)>>1;
		seg[now].lc=ins(seg[now].lc,l,m,tl,tr,w);
		seg[now].rc=ins(seg[now].rc,m+1,r,tl,tr,w);
		calc(now);
		return now;
	}
	int get(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i].sum;
		}
		int m=(l+r)>>1;
		return get(seg[i].lc,l,m,tl,tr)+get(seg[i].rc,m+1,r,tl,tr);
	}
	int pors(int top,int bot,int tr,int tl){
		//cout<<"get: "<<get(root[top],0,kaf-1,tl,tr)<<" hehe "<<get(root[bot-1],0,kaf-1,tl,tr)<<endl;	
		return get(root[top],0,kaf-1,tl,tr)-get(root[bot-1],0,kaf-1,tl,tr);
	}
	void build(){
		for(int i=0;i<maxn;i++){
			sort(all[i].begin(),all[i].end());
			all[i].resize(unique(all[i].begin(),all[i].end())-all[i].begin());
			for(auto x:all[i]){
				rt=ins(rt,0,kaf-1,x,x,1);
			}
			root[i]=rt;
		}
	}
}segv,segeo,segea,segr;
int mxr=-1,mxc=-1,mnr=maxn+10,mnc=maxn+10;

void add(int r,int c){
	//cout<<"addy: "<<r<<" "<<c<<endl;
	mnr=min(mnr,r);
	mxr=max(mxr,r);
	mnc=min(mnc,c);
	mxc=max(mxc,c);
	segv.add(r,c);
	segv.add(r,c+1);
	segv.add(r+1,c);
	segv.add(r+1,c+1);
	segeo.add(r,c);
	segeo.add(r+1,c);
	segea.add(r,c);
	segea.add(r,c+1);
	segr.add(r,c);
}

void build(){
	segv.build();
	segeo.build();
	segea.build();
	segr.build();
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	add(sr,sc);
	for(int i=0;i<M;i++){
		if(S[i]=='N'){
			sr--;
		}
		else if(S[i]=='S'){
			sr++;
		}else if(S[i]=='E'){
			sc++;
		}else{
			sc--;
		}
		add(sr,sc);
	}
	build();
}

int colour(int ar, int ac, int br, int bc) {
   	int v=segv.pors(br,ar+1,bc,ac+1)+(br-ar+2)*2+(bc-ac)*2;
   	int c=1;
   	int e=segeo.pors(br,ar+1,bc,ac)+segea.pors(br,ar,bc,ac+1)+(br-ar+1)*2+(bc-ac+1)*2;
   	int r=segr.pors(br,ar,bc,ac);
   	if(mnr>ar&&mxr<br&&mnc>ac&&mxc<bc){
   		c++;
   	}
   	int res=e-v+1+c-r-1;
   	return res;
}

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