Submission #738696

#	Time	Username	Problem	Language	Result	Execution time	Memory
738696		myrcella	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	960 ms	147220 KiB

rainbow

//by szh
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
 
#include "rainbow.h"
 
const int maxn = 1e6+10;
 
int r,c;
vector <pii> river;

struct psegtree{
	int rt[maxn<<4],tree[maxn<<4],ls[maxn<<4],rs[maxn<<4];
	vector <pii> pos;
	int tot;
	
	int update(int k,int l,int r,int root) {
		int cur = tot++;
		if (root==-1) tree[cur]=1;
		else tree[cur] = tree[root] + 1;
		ls[cur] = root==-1?-1:ls[root],rs[cur] = root==-1?-1:rs[root];
		if (l==r) return cur;
		int mid=l+r>>1;
		if (k<=mid) ls[cur] = update(k,l,mid,ls[cur]);
		else rs[cur] = update(k,mid+1,r,rs[cur]);
		return cur;
	}
	void init() {
		sort(ALL(pos));
		pos.erase(unique(ALL(pos)),pos.end());
		tot = 0;
		rt[0] = tot++,tree[0]=0,ls[0] = rs[0] = -1;
		rep(i,0,SZ(pos)) {
			rt[i+1] = update(pos[i].se,0,c,rt[i]);
			assert(tree[rt[i+1]]==i+1);
		}
	}
	int query(int node,int cl,int cr,int l,int r) {
		if (node==-1) return 0;
		if (l<=cl and cr<=r) return tree[node];
		int mid = cl+cr>>1;
		int ret = 0;
		if (l<=mid) ret += query(ls[node],cl,mid,l,r);
		if (r>mid) ret += query(rs[node],mid+1,cr,l,r);
		return ret;
	}
	int query(int ar,int ac,int br,int bc) {
		int ed = upper_bound(ALL(pos),MP(br,mod))-pos.begin();
		int bg = lower_bound(ALL(pos),MP(ar,-1))-pos.begin();
		return query(rt[ed],0,c,ac,bc) - query(rt[bg],0,c,ac,bc);
	}
}node,horizontal,vertical,grid;
int minr = mod,maxr=-1,minc = mod,maxc = -1;

void init(int R, int C, int sr, int sc, int M, char *S) {
	r = R, c = C;
	river.pb({sr,sc});
	minr = min(minr,sr),maxr = max(maxr,sr);
	minc = min(minc,sc),maxc = max(maxc,sc);
	rep(i,0,M) {
		if (S[i]=='S') sr++;
		else if (S[i]=='E') sc++;
		else if (S[i]=='W') sc--;
		else sr--;
		river.pb({sr,sc});
		minr = min(minr,sr),maxr = max(maxr,sr);
		minc = min(minc,sc),maxc = max(maxc,sc);
	}
	node.rt[0] = 0;
	horizontal.rt[0] = 0;
	vertical.rt[0] = 0;
	grid.rt[0] = 0;
	rep(i,0,SZ(river)) {
		node.pos.pb(river[i]);
		horizontal.pos.pb({river[i].fi,river[i].se-1});
		horizontal.pos.pb(river[i]);
		vertical.pos.pb({river[i].fi-1,river[i].se});
		vertical.pos.pb(river[i]);
		grid.pos.pb({river[i].fi-1,river[i].se});
		grid.pos.pb({river[i].fi,river[i].se-1});
		grid.pos.pb({river[i].fi-1,river[i].se-1});
		grid.pos.pb({river[i].fi,river[i].se});
	}
	node.init();
	horizontal.init();
	vertical.init();
	grid.init();
}
 
int colour(int ar, int ac, int br, int bc) {
	ll V = 1ll*(br-ar+1)*(bc-ac+1) - node.query(ar,ac,br,bc);
	ll E = 1ll*(br-ar+1)*(bc-ac) - horizontal.query(ar,ac,br,bc-1) 
	     + 1ll*(br-ar)*(bc-ac+1) - vertical.query(ar,ac,br-1,bc);
	ll F = 1ll*(br-ar)*(bc-ac) - grid.query(ar,ac,br-1,bc-1);
	
//	debug(V),debug(E),debug(F);
	
	if (ar<minr and ac<minc and br>maxr and bc>maxc) F++;
	return V-E+F;
}

Compilation message (stderr)

rainbow.cpp: In member function 'int psegtree::update(int, int, int, int)':
rainbow.cpp:42:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int mid=l+r>>1;
      |           ~^~
rainbow.cpp: In member function 'int psegtree::query(int, int, int, int, int)':
rainbow.cpp:60:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |   int mid = cl+cr>>1;
      |             ~~^~~

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