Submission #105968

#	Time	Username	Problem	Language	Result	Execution time	Memory
105968		username	Land of the Rainbow Gold (APIO17_rainbow)	C++14	12 / 100	534 ms	94824 KiB

rainbow

#include "rainbow.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef pair<int64_t,int64_t> pii;
typedef vector<int64_t> VI;
#define REP(i,j,k) for(int64_t i=(j);i<(k);++i)
#define ALL(a) a.begin(),a.end()
#define pb push_back
#define de(...) cerr<<__VA_ARGS__
#define ar(a,s,t) {REP(__i,s,t)de(a[__i]<<' ');de(endl);}
// default
const int64_t maxn=2e5+9;

struct FW{
	int64_t n;
	VI dat[maxn];
	void init(int64_t _n){
		n=_n;
		REP(i,0,n+1)dat[i].clear();
	}
	void add(int64_t x,int64_t y){
		for(int64_t i=x;i<=n;i+=i&-i){
			dat[i].pb(y);
		}
	}
	void proc(){
		REP(i,0,n+1)sort(ALL(dat[i]));
	}
	int64_t sum(int64_t x,int64_t y){
		int64_t re=0;
		for(int64_t i=x;i>0;i-=i&-i){
			re+=upper_bound(ALL(dat[i]),y)-dat[i].begin();
		}
		return re;
	}
}be1,be2,bf,bv;

set<pii>st,vt;

void init(int n,int m,int curx,int cury,int len,char*s){
	be1.init(n);
	be2.init(n+1);
	bf.init(n);
	bv.init(n+1);
	REP(i,0,len+1){
		if(!st.count(pii(curx,cury))){
			if(!st.count(pii(curx-1,cury)))be1.add(curx,cury);
			if(!st.count(pii(curx+1,cury)))be1.add(curx+1,cury);
			if(!st.count(pii(curx,cury-1)))be2.add(curx,cury);
			if(!st.count(pii(curx,cury+1)))be2.add(curx,cury+1);
			REP(x,curx,curx+2)REP(y,cury,cury+2){
				if(!vt.count(pii(x,y))){
					bv.add(x,y);
					vt.insert(pii(x,y));
				}
			}
			bf.add(curx,cury);
			st.insert(pii(curx,cury));
		}
		if(i<len){
			if(s[i]=='N')--curx;
			else if(s[i]=='E')++cury;
			else if(s[i]=='W')--cury;
			else ++curx; // S
		}
	}
	be1.proc();
	be2.proc();
	bf.proc();
	bv.proc();
}

int64_t calc(FW&fw,int64_t sx,int64_t sy,int64_t tx,int64_t ty){
	return fw.sum(tx,ty)-fw.sum(sx,ty)-fw.sum(tx,sy)+fw.sum(sx,sy);
}

int colour(int sx,int sy,int tx,int ty){
	int64_t e=calc(be1,sx,sy-1,tx,ty)+calc(be2,sx-1,sy,tx,ty)+2*(tx-sx+ty-sy+2);
	int64_t v=calc(bv,sx,sy,tx,ty)+2*(tx-sx+ty-sy+2);
	int64_t ff=calc(bf,sx-1,sy-1,tx,ty);
//	de("e = "<<e<<" , "<<"v = "<<v<<" , "<<"ff = "<<ff<<endl);
	return e-v+2-ff-1;
}

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