제출 #57364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57364		IvanC	무지개나라 (APIO17_rainbow)	C++17	11 / 100	272 ms	69932 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 60;
const int MAXL = 2*1e5 + 10;
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};
 
struct node{
	int pref[2],suf[2],componentes,l0,r0,l1,r1,s0,s1;
	
	node(int v0 = 0,int v1 = 0){
		pref[0] = v0;pref[1] = v1;
		suf[0] = v0;suf[1] = v1;
		l0 = r0 = s0 = v0;
		l1 = r1 = s1 = v1;
		componentes = max(s0,s1);
	}
	
	node operator+(const node& other )const{
		node novo;
		novo.pref[0] = pref[0];novo.pref[1] = pref[1];
		novo.suf[0] = other.suf[0];novo.suf[1] = suf[1];
		novo.l0 = l0;novo.l1 = l1;
		novo.r0 = other.r0;novo.r1 = other.r1;
		novo.s0 = s0 + other.s0;
		novo.s1 = s1 + other.s1;
		novo.componentes = componentes + other.componentes;
		if(suf[0] == 0 && suf[1] == 0){
			if(other.pref[0] == 0 && other.pref[1] == 0){
				
			}
			else if(other.pref[0] == 1 && other.pref[1] == 0){
				
			}
			else if(other.pref[0] == 0 && other.pref[1] == 1){
				
			}
			else{
				
			}
		}	
		else if(suf[0] == 1 && suf[1] == 0){
			if(other.pref[0] == 0 && other.pref[1] == 0){
				
			}
			else if(other.pref[0] == 1 && other.pref[1] == 0){
				novo.componentes--;
				novo.s0--;
			}
			else if(other.pref[0] == 0 && other.pref[1] == 1){
				
			}
			else{
				novo.componentes--;
				novo.s0--;
			}
		}
		else if(suf[0] == 0 && suf[1] == 1){
			if(other.pref[0] == 0 && other.pref[1] == 0){
				
			}
			else if(other.pref[0] == 1 && other.pref[1] == 0){
				
			}
			else if(other.pref[0] == 0 && other.pref[1] == 1){
				novo.componentes--;
				novo.s1--;
			}
			else{
				novo.componentes--;
				novo.s1--;
			}
		}
		else{
			if(other.pref[0] == 0 && other.pref[1] == 0){
				
			}
			else if(other.pref[0] == 1 && other.pref[1] == 0){
				novo.componentes--;
				novo.s0--;
			}
			else if(other.pref[0] == 0 && other.pref[1] == 1){
				novo.componentes--;
				novo.s1--;
			}
			else{
				novo.componentes--;
				novo.s0--;
				novo.s1--;
			}
		}
		return novo;
	}
	
};
 
int matriz[MAXN][MAXN],tamx,tamy;
int tabela[3][MAXL];
int processado[MAXN][MAXN];
int lo_x,lo_y,hi_x,hi_y;
node seg[4*MAXL];
 
inline int valido(int x,int y){
	return x >= lo_x && y >= lo_y && x <= hi_x && y <= hi_y && matriz[x][y] != 1; 
}
 
void dfs(int x,int y){
	if(processado[x][y]) return;
	//printf("DFS %d %d\n",x,y);
	processado[x][y] = 1;
	for(int i = 0;i<4;i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(valido(nx,ny)) dfs(nx,ny);
	}
}
 
void build(int pos,int left,int right){
	//printf("P %d L %d R %d\n",pos,left,right);
	if(left == right){
		seg[pos] = node(1 - tabela[1][left],1 - tabela[2][left]);
		return;
	}
	int mid = (left + right)/2;
	build(2*pos,left,mid);
	build(2*pos+1,mid+1,right);
	seg[pos] = seg[2*pos] + seg[2*pos+1];
}
 
node query(int pos,int left,int right,int i,int j){
	if(left >= i && right <= j){
		return seg[pos];
	}
	int mid = (left+right)/2;
	if(j <= mid) return query(2*pos,left,mid,i,j);
	else if(i >= mid + 1) return query(2*pos+1,mid+1,right,i,j);
	else return query(2*pos,left,mid,i,j) + query(2*pos+1,mid+1,right,i,j);
}
 
void init(int R, int C, int sr, int sc, int M, char *S) {
	tamx = R;tamy= C;
	if(tamx <= 50 && tamy <= 50){
		matriz[sr][sc] = 1;
		for(int vez = 0;vez<M;vez++){
			if(S[vez] == 'N'){
				//printf("N\n");
				sr--;
			}
			else if(S[vez] == 'W'){
				//printf("W\n");
				sc--;
			}
			else if(S[vez] == 'S'){
				//printf("S\n");
				sr++;
			}
			else{
				//printf("E\n");
				sc++;
			}
			//printf("%d %d\n",sr,sc);
			matriz[sr][sc] = 1;
		}
		//for(int i = 1;i<=tamx;i++){
		//	for(int j = 1;j<=tamy;j++){
		//		printf("%d",matriz[i][j]);
		//	}
		//	printf("\n");
		//}
	}
	else{
		tabela[sr][sc] = 1;
		for(int vez = 0;vez<M;vez++){
			if(S[vez] == 'N'){
				//printf("N\n");
				sr--;
			}
			else if(S[vez] == 'W'){
				//printf("W\n");
				sc--;
			}
			else if(S[vez] == 'S'){
				//printf("S\n");
				sr++;
			}
			else{
				//printf("E\n");
				sc++;
			}
			//printf("%d %d\n",sr,sc);
			tabela[sr][sc] = 1;
		}
		build(1,1,tamy);
	}
}
 
int colour(int ar, int ac, int br, int bc) {
    if(tamx <= 50 && tamy <= 50){
		memset(processado,0,sizeof(processado));
    		int total = 0;
    		lo_x = ar;lo_y = ac;
    		hi_x = br;hi_y = bc;
    		for(int i = ar;i<=br;i++){
    			for(int j = ac;j <= bc;j++){
    				if(matriz[i][j] == 1 || processado[i][j]) continue;
    				//printf("Componente nova\n");
    				dfs(i,j);
    				total++;
    			}
    		}
    		return total;
	}
	else{
		node resposta = query(1,1,tamy,ac,bc);
		if(ar == 1 && br == 1){
			return resposta.s0;
		}
		else if(ar == 2 && br == 2){
			return resposta.s1;
		}
		else{
			return resposta.componentes;
		}
	}
}

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