Submission #50070

#	Time	Username	Problem	Language	Result	Execution time	Memory
50070		hamzqq9	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	130 ms	21672 KiB

rainbow

#include "rainbow.h"
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 4000000000000000000ll
#define MAXN 200005
#define LOG 20
#define magic 100
#define KOK 350
#define EPS 0.0025
#define pw(x) ((1ll)<<(x))
#define PI 3.1415926535
using namespace std;

struct seg {

	int pre;
	int suf;
	int ins;
	int full;

} Sg[MAXN*4];

int lazy[MAXN*4];
int reg,R,C;
int bol[55][MAXN],nxt[3][MAXN],prv[3][MAXN],pres[3][MAXN];
bool vis[55][MAXN],a[55][MAXN];
vector<iii> qu[MAXN];
vector<int> eve[MAXN];
int w[4][2]={1,0,0,1,-1,0,0,-1};

void inc(int &x,int &y,char c) {

	if(c=='N') x--;
	if(c=='S') x++;
	if(c=='W') y--;
	if(c=='E') y++;

}

void clear(int x,int y) {

	for(int i=0;i<=x;i++) for(int j=0;j<=y;j++) vis[i][j]=bol[i][j]=0;

	reg=0;

}

void push(int node) {

	lazy[node*2]=lazy[node];
	lazy[node*2+1]=lazy[node];
	lazy[node]=0;

}

seg merge(seg x,seg y) {

	seg res;

	res.pre=x.pre+(x.full)*y.pre;
	res.suf=y.suf+(y.full)*x.suf;
	res.full=(x.full&y.full);
	res.ins=x.ins+y.ins+(x.suf>0 && y.pre>0 && !x.full && !y.full);

	return res;

}
 
seg get(int node,int bas,int son,int x,int y,int flag) {

	if(bas>y || son<x) return {0,0,0,1}; 

	if(bas>=x && son<=y) {

		if(flag==1) return {son-bas+1,son-bas+1,0,1};
		if(flag==2) return {0,0,0,0};

		return Sg[node];

	}

	if(!flag) flag=lazy[node];

	return merge(get(node*2,bas,orta,x,y,flag),get(node*2+1,orta+1,son,x,y,flag));

}

void up(int node,int bas,int son,int x,int y,int val) {

	if(bas>y || son<x) return ;

	if(bas>=x && son<=y) {

		lazy[node]=val;

		return ;

	}

	push(node);

	up(node*2,bas,orta,x,y,val);
	up(node*2+1,orta+1,son,x,y,val);

	if(lazy[node*2]==2 && lazy[node*2+1]==2) {

		Sg[node].pre=0;
		Sg[node].suf=0;
		Sg[node].ins=0;

	}
	else if(lazy[node*2]==2) {

		Sg[node].pre=0;
		Sg[node].suf=Sg[node*2+1].suf;
		Sg[node].ins=Sg[node*2+1].ins+(Sg[node*2+1].pre>0);

	}
	else if(lazy[node*2+1]==2) {

		Sg[node].pre=Sg[node*2].pre;
		Sg[node].suf=0;
		Sg[node].ins=Sg[node*2].ins+(Sg[node*2].suf>0);

	}
	else {

		Sg[node]=merge(Sg[node*2],Sg[node*2+1]);

	}

}

void build(int node,int bas,int son) {

	if(bas==son) {

		Sg[node]={1,1,0,1};

		return ;

	}

	build(node*2,bas,orta);
	build(node*2+1,orta+1,son);

	Sg[node]=merge(Sg[node*2],Sg[node*2+1]);

}

void dfs(int x,int y,int lx,int ly,int rx,int ry) {

	if(vis[x][y] || a[x][y]) return ;

	if(x>rx || x<lx || y>ry || y<ly) return ;

	bol[x][y]=reg;
	vis[x][y]=1;

	for(int i=0;i<4;i++) dfs(x+w[i][0],y+w[i][1],lx,ly,rx,ry);

} 

void fillnaive(int R,int C,int sr,int sc,int M,char *S) {

	a[sr][sc]=1;

	for(int i=0;i<M;i++) {

		inc(sr,sc,S[i]);

		a[sr][sc]=1;

	}

	if(R==2) {

		clear(R,C);

		for(int j=1;j<=C;j++) {

			for(int i=1;i<=R;i++) {

				if(!vis[i][j] && !a[i][j]) {

					reg++;

					dfs(i,j,1,1,R,C);

				}

			}

		}

		for(int i=1;i<=R;i++) {

			for(int j=1;j<=C;j++) {

				if(!a[i][j] && (a[i][j-1] || j-1==0)) pres[i][j]=pres[i][j-1]+1;
				else pres[i][j]=pres[i][j-1];

			}

		}

		for(int i=1;i<=R;i++) {

			for(int j=C;j>=1;j--) {

				if(bol[i][j]) nxt[i][j]=bol[i][j];
				else nxt[i][j]=nxt[i][j+1];

			}

			for(int j=1;j<=C;j++) {

				if(bol[i][j]) prv[i][j]=bol[i][j];
				else prv[i][j]=prv[i][j-1];

			}

		}

	}

}

void init(int R, int C, int sr, int sc, int M, char *S) {

	::R=R;
	::C=C;

	if((R<=50 && C<=50) || R<=2) {

		fillnaive(R,C,sr,sc,M,S);

	}
	else {

		eve[sr].pb(sc);

		for(int i=0;i<M;i++) {

			inc(sr,sc,S[i]);

			eve[sr].pb(sc);

		}

		for(int i=1;i<MAXN;i++) {

			eve[i].erase(unique(all(eve[i])),eve[i].end());

			if(!sz(eve[i])) {

				qu[i].pb({{0,MAXN-1},0});

				continue ;

			}

			qu[i].pb({{0,eve[i][0]-1},0});

			for(int j=0;j<sz(eve[i]);j++) {

				int bas=j;

				while(j+1<sz(eve[i]) && eve[i][j]==eve[i][j+1]) j++;

				qu[i].pb({{eve[i][bas],eve[i][j]},1});

				if(j+1<sz(eve[i])) {

					qu[i].pb({{eve[i][j]+1,eve[i][j+1]-1},0});

				}
				else {

					qu[i].pb({{eve[i][j]+1,MAXN-1},0});

				}

			}

		}

	}

}

int colour(int ar, int ac, int br, int bc) {
    
	if(R<=2) {

		if(ar!=br) {

			int r1=min(nxt[ar][ac],nxt[br][ac]);
			int r2=max(prv[br][bc],prv[ar][bc]);

			return max(0,r2-r1+1);

		}

		return pres[ar][bc]-pres[ar][ac-1]+(!a[ar][ac] && !a[ar][ac-1]);


	}

	if(R<=50 && C<=50) {

		clear(R,C);

		for(int i=ar;i<=br;i++) {

			for(int j=ac;j<=bc;j++) {

				if(!vis[i][j] && !a[i][j]) {

					reg++;

					dfs(i,j,ar,ac,br,bc);

				}

			}

		}

		return reg;

	}

	build(1,ac,bc);

	lazy[1]=1;

	int res=0;

	for(int i=ar;i<=br;i++) {

		for(iii j:qu[i]) {

			if(j.st.nd<ac || j.st.st>bc) continue ;

			int l=max(j.st.st,ac);
			int r=min(j.st.nd,bc);

			if(j.nd) {
			
				seg query=get(1,ac,bc,l,r,0);

				res+=query.ins+(query.pre>0)+(query.suf>0)-(query.pre && query.suf && query.pre==query.suf);

			}

			up(1,ac,bc,l,r,j.nd+1);

		}

	}

	return res;

}

Compilation message (stderr)

rainbow.cpp: In function 'void clear(int, int)':
rainbow.cpp:71:65: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  for(int i=0;i<=x;i++) for(int j=0;j<=y;j++) vis[i][j]=bol[i][j]=0;
                                                        ~~~~~~~~~^~

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