Submission #471430

#	Time	Username	Problem	Language	Result	Execution time	Memory
471430		CSQ31	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	1201 ms	124744 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
int r,c;
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define pb push_back
typedef pair<int,int> pii;
const int MAXN = 2e5;
struct fen{
	vector<vector<int>>bit;
	vector<set<int>>data;
	int r,c;
	fen(){}
	fen(int _r,int _c){
		r = _r;
		c = _c;
		bit.resize(r+1);
		data.resize(r+1);
	}
	
	void add(int x,int y){
		data[x].insert(y);
	}
	int query(int x,int l,int r){
		int res = 0;
		for(int i=x;i;i-=i&(-i)){
			int p = lower_bound(all(bit[i]),l) - bit[i].begin();
			int q = upper_bound(all(bit[i]),r) - bit[i].begin();
			res+=q-p;
		}
		return res;
	}
	int query(int xl,int xr,int yl,int yr){
		if(xl > xr)return 0;
		return query(xr,yl,yr) - query(xl-1,yl,yr);
	}
	
	void build(){
		for(int i=1;i<=r;i++){
			for(int j=i;j<=r;j+=j&(-j)){
				for(int x:data[i])bit[j].pb(x);
			}
		}
		for(int i=1;i<=r;i++)sort(all(bit[i]));
	}
}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 = fen(r,c);
	hedge = fen(r+1,c);
	vedge = fen(r,c+1);
	vert = fen(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