oj.uz

Submission #50073

# Submission time Handle Problem Language Result Execution time Memory
50073 2018-06-07T10:02:48 Z hamzqq9 Land of the Rainbow Gold (APIO17_rainbow) C++14
23 / 100
 3000 ms 42100 KB 
#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 1000000000
#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++) {

			nxt[i][C+1]=inf;
			prv[i][0]=-inf;

			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]);

			if(r1==inf || r2==-inf) return 0;

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

		}

		return pres[ar][bc]-pres[ar][ac-1]+(!a[ar][ac] && !a[ar][ac-1] && 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

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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9976 KB Output is correct
2 Correct 19 ms 10596 KB Output is correct
3 Correct 29 ms 10792 KB Output is correct
4 Correct 29 ms 10792 KB Output is correct
5 Correct 20 ms 10792 KB Output is correct
6 Correct 9 ms 10792 KB Output is correct
7 Correct 9 ms 10792 KB Output is correct
8 Correct 10 ms 10792 KB Output is correct
9 Correct 9 ms 10792 KB Output is correct
10 Correct 9 ms 10792 KB Output is correct
11 Correct 34 ms 10824 KB Output is correct
12 Correct 25 ms 10832 KB Output is correct
13 Correct 26 ms 10848 KB Output is correct
14 Correct 19 ms 10912 KB Output is correct
15 Correct 10 ms 10912 KB Output is correct
16 Correct 9 ms 10912 KB Output is correct
17 Correct 10 ms 10912 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10912 KB Output is correct
2 Correct 10 ms 10912 KB Output is correct
3 Correct 121 ms 40160 KB Output is correct
4 Correct 133 ms 40160 KB Output is correct
5 Correct 118 ms 40160 KB Output is correct
6 Correct 115 ms 42028 KB Output is correct
7 Correct 118 ms 42100 KB Output is correct
8 Correct 112 ms 42100 KB Output is correct
9 Correct 117 ms 42100 KB Output is correct
10 Correct 129 ms 42100 KB Output is correct
11 Correct 127 ms 42100 KB Output is correct
12 Correct 105 ms 42100 KB Output is correct
13 Correct 105 ms 42100 KB Output is correct
14 Correct 117 ms 42100 KB Output is correct
15 Correct 121 ms 42100 KB Output is correct
16 Correct 114 ms 42100 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10912 KB Output is correct
2 Incorrect 74 ms 42100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9976 KB Output is correct
2 Correct 19 ms 10596 KB Output is correct
3 Correct 29 ms 10792 KB Output is correct
4 Correct 29 ms 10792 KB Output is correct
5 Correct 20 ms 10792 KB Output is correct
6 Correct 9 ms 10792 KB Output is correct
7 Correct 9 ms 10792 KB Output is correct
8 Correct 10 ms 10792 KB Output is correct
9 Correct 9 ms 10792 KB Output is correct
10 Correct 9 ms 10792 KB Output is correct
11 Correct 34 ms 10824 KB Output is correct
12 Correct 25 ms 10832 KB Output is correct
13 Correct 26 ms 10848 KB Output is correct
14 Correct 19 ms 10912 KB Output is correct
15 Correct 10 ms 10912 KB Output is correct
16 Correct 9 ms 10912 KB Output is correct
17 Correct 10 ms 10912 KB Output is correct
18 Execution timed out 3044 ms 42100 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9976 KB Output is correct
2 Correct 19 ms 10596 KB Output is correct
3 Correct 29 ms 10792 KB Output is correct
4 Correct 29 ms 10792 KB Output is correct
5 Correct 20 ms 10792 KB Output is correct
6 Correct 9 ms 10792 KB Output is correct
7 Correct 9 ms 10792 KB Output is correct
8 Correct 10 ms 10792 KB Output is correct
9 Correct 9 ms 10792 KB Output is correct
10 Correct 9 ms 10792 KB Output is correct
11 Correct 34 ms 10824 KB Output is correct
12 Correct 25 ms 10832 KB Output is correct
13 Correct 26 ms 10848 KB Output is correct
14 Correct 19 ms 10912 KB Output is correct
15 Correct 10 ms 10912 KB Output is correct
16 Correct 9 ms 10912 KB Output is correct
17 Correct 10 ms 10912 KB Output is correct
18 Execution timed out 3044 ms 42100 KB Time limit exceeded
19 Halted 0 ms 0 KB -