제출 #471427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
471427		CSQ31	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	1482 ms	477316 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
int r,c;
#define fi first
#define se second
typedef pair<int,int> pii;
struct node {
	node *L = NULL,*R=NULL;
	int val = 0;
	node(){};
	node(int v){val = v;}
	node(node *_L,node *_R){
		L = _L;
		R = _R;
		val = ((L==NULL)?0:L->val) + ((R==NULL)?0:R->val);
	}
};
const int MAXN = 2e5;
struct seg{
	vector<node*>root;
	vector<set<int>>d;
	void add(int x,int y){d[x].insert(y);}
	int r,c;
	seg(){}
	seg(int _r,int _c){
		r = _r;
		c = _c;
		root.resize(r+1);
		d.resize(r+1);
		root[0] = new node();
	}
	
	node* upd(node *v,int l,int r,int pos){
		if(l == r)return new node(v->val+1);
		int tm = (l+r)/2;
		if(pos <=tm){
			if(v->L == NULL)v->L = new node();
			return new node(upd(v->L,l,tm,pos), v->R);
		}else{
			if(v->R == NULL)v->R = new node();
			return new node(v->L, upd(v->R,tm+1,r,pos));	
		}
	}
	int query(node *b,int l,int r,int tl,int tr){
		if(l>r || !b)return 0;
		if(l==tl && r==tr)return b->val;
		int tm = (tl+tr)/2;
		return query(b->L,l,min(r,tm),tl,tm)+query(b->R,max(l,tm+1),r,tm+1,tr);
	}
	int query(int xl,int xr,int yl,int yr){
		if(xl > xr)return 0;
		return query(root[xr],yl,yr,1,c) - query(root[xl-1],yl,yr,1,c);
	}
	
	void build(){
		for(int i=1;i<=r;i++){
			root[i] = new node(root[i-1]->L,root[i-1]->R);
			for(int x:d[i])root[i] = upd(root[i],1,c,x);
		}
	}
}river,hedge,vedge,vert;
pii mx = {-1e9,-1e9};
pii mn = {1e9,1e9};
void init(int R, int C, int sr, int sc, int M, char *S) {
	r = R;
	c = C;
	river = seg(r,c);
	hedge = seg(r+1,c);
	vedge = seg(r,c+1);
	vert = seg(r+1,c+1);
	int x = sr;
	int y = sc;
	river.add(x,y);
	hedge.add(x,y);
	hedge.add(x+1,y);
	vedge.add(x,y);
	vedge.add(x,y+1);
	vert.add(x,y);
	vert.add(x+1,y);
	vert.add(x,y+1);
	vert.add(x+1,y+1);
	mx.fi = max(mx.fi,x);
	mx.se = max(mx.se,y);
	mn.fi = min(mn.fi,x);
	mn.se = min(mn.se,y);
	for(int i=0;i<M;i++){
		char c = S[i];
		if(c =='N')x--;
		if(c =='S')x++;
		if(c =='W')y--;
		if(c =='E')y++;
		river.add(x,y);
		hedge.add(x,y);
		hedge.add(x+1,y);
		vedge.add(x,y);
		vedge.add(x,y+1);
		vert.add(x,y);
		vert.add(x+1,y);
		vert.add(x,y+1);
		vert.add(x+1,y+1);
		mx.fi = max(mx.fi,x);
		mx.se = max(mx.se,y);
		mn.fi = min(mn.fi,x);
		mn.se = min(mn.se,y);
	}
	
	river.build();
	vert.build();
	hedge.build();
	vedge.build();
}

int colour(int ar, int ac, int br, int bc) {
	int C = (!(mn.fi <= ar || mn.se <= ac || mx.fi >= br || mx.se >= bc)) + 1;
	int A = river.query(ar,br,ac,bc);
	int V = vert.query(ar+1,br,ac+1,bc);
	int E = hedge.query(ar+1,br,ac,bc) + vedge.query(ar,br,ac+1,bc);
	//cout<<E<<" "<<V<<" "<<A<<" "<<C<<'\n';
	int F = 1+C+E-V;
    return F - A - 1;
}

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