oj.uz

Submission #105968

# Submission time Handle Problem Language Result Execution time Memory
105968 2019-04-16T03:04:03 Z username Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 534 ms 94824 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19200 KB Output is correct
2 Correct 29 ms 19456 KB Output is correct
3 Incorrect 24 ms 19200 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19192 KB Output is correct
2 Correct 23 ms 19200 KB Output is correct
3 Correct 350 ms 37552 KB Output is correct
4 Correct 485 ms 47632 KB Output is correct
5 Correct 461 ms 47424 KB Output is correct
6 Correct 353 ms 41808 KB Output is correct
7 Correct 428 ms 41976 KB Output is correct
8 Correct 99 ms 22944 KB Output is correct
9 Correct 534 ms 47676 KB Output is correct
10 Correct 475 ms 47548 KB Output is correct
11 Correct 373 ms 41992 KB Output is correct
12 Correct 331 ms 45632 KB Output is correct
13 Correct 381 ms 47412 KB Output is correct
14 Correct 340 ms 47420 KB Output is correct
15 Correct 289 ms 41908 KB Output is correct
16 Correct 393 ms 40896 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19200 KB Output is correct
2 Correct 444 ms 83724 KB Output is correct
3 Correct 438 ms 88908 KB Output is correct
4 Correct 477 ms 94824 KB Output is correct
5 Correct 366 ms 71256 KB Output is correct
6 Correct 163 ms 32964 KB Output is correct
7 Incorrect 228 ms 41760 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19200 KB Output is correct
2 Correct 29 ms 19456 KB Output is correct
3 Incorrect 24 ms 19200 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19200 KB Output is correct
2 Correct 29 ms 19456 KB Output is correct
3 Incorrect 24 ms 19200 KB Output isn't correct
4 Halted 0 ms 0 KB -