oj.uz

답안 #57357

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
57357 2018-07-14T15:52:59 Z IvanC 무지개나라 (APIO17_rainbow) C++17
11 / 100
 26 ms 1448 KB 
#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*MAXN];

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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 14 ms 376 KB Output is correct
3 Correct 26 ms 684 KB Output is correct
4 Correct 25 ms 684 KB Output is correct
5 Correct 9 ms 684 KB Output is correct
6 Correct 3 ms 684 KB Output is correct
7 Correct 2 ms 684 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 2 ms 696 KB Output is correct
10 Correct 3 ms 696 KB Output is correct
11 Correct 23 ms 768 KB Output is correct
12 Correct 18 ms 768 KB Output is correct
13 Correct 10 ms 768 KB Output is correct
14 Correct 8 ms 768 KB Output is correct
15 Correct 0 ms 768 KB Output is correct
16 Correct 2 ms 768 KB Output is correct
17 Correct 4 ms 768 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 768 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Runtime error 5 ms 1448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 768 KB Output is correct
2 Runtime error 4 ms 1448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 14 ms 376 KB Output is correct
3 Correct 26 ms 684 KB Output is correct
4 Correct 25 ms 684 KB Output is correct
5 Correct 9 ms 684 KB Output is correct
6 Correct 3 ms 684 KB Output is correct
7 Correct 2 ms 684 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 2 ms 696 KB Output is correct
10 Correct 3 ms 696 KB Output is correct
11 Correct 23 ms 768 KB Output is correct
12 Correct 18 ms 768 KB Output is correct
13 Correct 10 ms 768 KB Output is correct
14 Correct 8 ms 768 KB Output is correct
15 Correct 0 ms 768 KB Output is correct
16 Correct 2 ms 768 KB Output is correct
17 Correct 4 ms 768 KB Output is correct
18 Runtime error 4 ms 1448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 14 ms 376 KB Output is correct
3 Correct 26 ms 684 KB Output is correct
4 Correct 25 ms 684 KB Output is correct
5 Correct 9 ms 684 KB Output is correct
6 Correct 3 ms 684 KB Output is correct
7 Correct 2 ms 684 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 2 ms 696 KB Output is correct
10 Correct 3 ms 696 KB Output is correct
11 Correct 23 ms 768 KB Output is correct
12 Correct 18 ms 768 KB Output is correct
13 Correct 10 ms 768 KB Output is correct
14 Correct 8 ms 768 KB Output is correct
15 Correct 0 ms 768 KB Output is correct
16 Correct 2 ms 768 KB Output is correct
17 Correct 4 ms 768 KB Output is correct
18 Runtime error 4 ms 1448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -