답안 #50069 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50069	2018-06-07T09:29:34 Z	hamzqq9	무지개나라 (APIO17_rainbow)	C++14	0 / 100	72 ms	21608 KB

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

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.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	10104 KB	Output is correct
2	Correct	21 ms	10592 KB	Output is correct
3	Correct	41 ms	10908 KB	Output is correct
4	Correct	33 ms	10908 KB	Output is correct
5	Correct	20 ms	10908 KB	Output is correct
6	Correct	10 ms	10908 KB	Output is correct
7	Correct	9 ms	10908 KB	Output is correct
8	Correct	9 ms	10908 KB	Output is correct
9	Correct	9 ms	10908 KB	Output is correct
10	Correct	9 ms	10908 KB	Output is correct
11	Correct	33 ms	10908 KB	Output is correct
12	Correct	26 ms	10908 KB	Output is correct
13	Correct	23 ms	10908 KB	Output is correct
14	Correct	19 ms	10908 KB	Output is correct
15	Correct	9 ms	10908 KB	Output is correct
16	Incorrect	9 ms	10908 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	9 ms	10908 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	10908 KB	Output is correct
2	Incorrect	72 ms	21608 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	10104 KB	Output is correct
2	Correct	21 ms	10592 KB	Output is correct
3	Correct	41 ms	10908 KB	Output is correct
4	Correct	33 ms	10908 KB	Output is correct
5	Correct	20 ms	10908 KB	Output is correct
6	Correct	10 ms	10908 KB	Output is correct
7	Correct	9 ms	10908 KB	Output is correct
8	Correct	9 ms	10908 KB	Output is correct
9	Correct	9 ms	10908 KB	Output is correct
10	Correct	9 ms	10908 KB	Output is correct
11	Correct	33 ms	10908 KB	Output is correct
12	Correct	26 ms	10908 KB	Output is correct
13	Correct	23 ms	10908 KB	Output is correct
14	Correct	19 ms	10908 KB	Output is correct
15	Correct	9 ms	10908 KB	Output is correct
16	Incorrect	9 ms	10908 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	10104 KB	Output is correct
2	Correct	21 ms	10592 KB	Output is correct
3	Correct	41 ms	10908 KB	Output is correct
4	Correct	33 ms	10908 KB	Output is correct
5	Correct	20 ms	10908 KB	Output is correct
6	Correct	10 ms	10908 KB	Output is correct
7	Correct	9 ms	10908 KB	Output is correct
8	Correct	9 ms	10908 KB	Output is correct
9	Correct	9 ms	10908 KB	Output is correct
10	Correct	9 ms	10908 KB	Output is correct
11	Correct	33 ms	10908 KB	Output is correct
12	Correct	26 ms	10908 KB	Output is correct
13	Correct	23 ms	10908 KB	Output is correct
14	Correct	19 ms	10908 KB	Output is correct
15	Correct	9 ms	10908 KB	Output is correct
16	Incorrect	9 ms	10908 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

답안 #50069

Compilation message

Subtask #1 0 / 11.0

Subtask #2 0 / 12.0

Subtask #3 0 / 24.0

Subtask #4 0 / 27.0

Subtask #5 0 / 26.0

Subtask #1
0 / 11.0

Subtask #2
0 / 12.0

Subtask #3
0 / 24.0

Subtask #4
0 / 27.0

Subtask #5
0 / 26.0