제출 #930936

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

rainbow

#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
long long kaf=(1<<19);

struct segment{
	vector<long long>all[maxn];
	void add(long long r,long long c){
		all[r].push_back(c);
	}	
	struct node{
		long long lc,rc,sum;
		node(){
			lc=rc=sum=0;
		}
	};
	node seg[(1<<20)*20];
	long long root[maxn],rt=0,nx=1;
	void calc(long long i){
		seg[i].sum=seg[seg[i].lc].sum+seg[seg[i].rc].sum;
	}
	long long ins(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return i;
		}
		long long now=nx;
		seg[nx]=seg[i];
		nx++;
		if(l>=tl&&r<=tr){
			seg[nx-1].sum+=w;
			return nx-1;
		}
		long long 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;
	}
	long long get(long long i,long long l,long long r,long long tl,long long tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i].sum;
		}
		long long m=(l+r)>>1;
		return get(seg[i].lc,l,m,tl,tr)+get(seg[i].rc,m+1,r,tl,tr);
	}
	long long pors(long long top,long long bot,long long tr,long long 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(long long 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;
long long mxr=-1,mxc=-1,mnr=maxn+10,mnc=maxn+10;

void add(long long r,long long c){
	//cout<<"addy: "<<r<<" "<<c<<endl;
	mnr=min(mnr,r);
	mxr=max(mxr,r);
	mnc=min(mnc,c);
	mxc=min(mnc,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(long long 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();
}

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

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