| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 105965 | username | Land of the Rainbow Gold (APIO17_rainbow) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rainbow.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define int int_fast64_t
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> VI;
#define REP(i,j,k) for(int 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
#define short int_fast32_t
const int maxn=2e5+9;
struct FW{
int n;
VI dat[maxn];
void init(int _n){
n=_n;
REP(i,0,n+1)dat[i].clear();
}
void add(int x,int y){
for(int i=x;i<=n;i+=i&-i){
dat[i].pb(y);
}
}
void proc(){
REP(i,0,n+1)sort(ALL(dat[i]));
}
int sum(int x,int y){
int re=0;
for(int 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(short n,short m,short curx,short cury,short len,string 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();
}
int calc(FW&fw,int sx,int sy,int tx,int ty){
return fw.sum(tx,ty)-fw.sum(sx,ty)-fw.sum(tx,sy)+fw.sum(sx,sy);
}
short colour(short sx,short sy,short tx,short ty){
int e=calc(be1,sx,sy-1,tx,ty)+calc(be2,sx-1,sy,tx,ty)+2*(tx-sx+ty-sy+2);
int v=calc(bv,sx,sy,tx,ty)+2*(tx-sx+ty-sy+2);
int ff=calc(bf,sx-1,sy-1,tx,ty);
de("e = "<<e<<" , "<<"v = "<<v<<" , "<<"ff = "<<ff<<endl);
return e-v+2-ff-1;
}