oj.uz

답안 #57364

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
57364 2018-07-14T16:23:54 Z IvanC 무지개나라 (APIO17_rainbow) C++17
11 / 100
 272 ms 69932 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*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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 34808 KB Output is correct
2 Correct 54 ms 34808 KB Output is correct
3 Correct 49 ms 34992 KB Output is correct
4 Correct 64 ms 35084 KB Output is correct
5 Correct 37 ms 35084 KB Output is correct
6 Correct 30 ms 35084 KB Output is correct
7 Correct 29 ms 35084 KB Output is correct
8 Correct 34 ms 35084 KB Output is correct
9 Correct 30 ms 35100 KB Output is correct
10 Correct 35 ms 35100 KB Output is correct
11 Correct 61 ms 35184 KB Output is correct
12 Correct 49 ms 35184 KB Output is correct
13 Correct 46 ms 35184 KB Output is correct
14 Correct 35 ms 35184 KB Output is correct
15 Correct 33 ms 35184 KB Output is correct
16 Correct 30 ms 35184 KB Output is correct
17 Correct 38 ms 35184 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 35184 KB Output is correct
2 Correct 38 ms 35184 KB Output is correct
3 Incorrect 272 ms 36268 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 35184 KB Output is correct
2 Runtime error 75 ms 69932 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 34 ms 34808 KB Output is correct
2 Correct 54 ms 34808 KB Output is correct
3 Correct 49 ms 34992 KB Output is correct
4 Correct 64 ms 35084 KB Output is correct
5 Correct 37 ms 35084 KB Output is correct
6 Correct 30 ms 35084 KB Output is correct
7 Correct 29 ms 35084 KB Output is correct
8 Correct 34 ms 35084 KB Output is correct
9 Correct 30 ms 35100 KB Output is correct
10 Correct 35 ms 35100 KB Output is correct
11 Correct 61 ms 35184 KB Output is correct
12 Correct 49 ms 35184 KB Output is correct
13 Correct 46 ms 35184 KB Output is correct
14 Correct 35 ms 35184 KB Output is correct
15 Correct 33 ms 35184 KB Output is correct
16 Correct 30 ms 35184 KB Output is correct
17 Correct 38 ms 35184 KB Output is correct
18 Runtime error 73 ms 69932 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 34 ms 34808 KB Output is correct
2 Correct 54 ms 34808 KB Output is correct
3 Correct 49 ms 34992 KB Output is correct
4 Correct 64 ms 35084 KB Output is correct
5 Correct 37 ms 35084 KB Output is correct
6 Correct 30 ms 35084 KB Output is correct
7 Correct 29 ms 35084 KB Output is correct
8 Correct 34 ms 35084 KB Output is correct
9 Correct 30 ms 35100 KB Output is correct
10 Correct 35 ms 35100 KB Output is correct
11 Correct 61 ms 35184 KB Output is correct
12 Correct 49 ms 35184 KB Output is correct
13 Correct 46 ms 35184 KB Output is correct
14 Correct 35 ms 35184 KB Output is correct
15 Correct 33 ms 35184 KB Output is correct
16 Correct 30 ms 35184 KB Output is correct
17 Correct 38 ms 35184 KB Output is correct
18 Runtime error 73 ms 69932 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -