oj.uz

Submission #57354

# Submission time Handle Problem Language Result Execution time Memory
57354 2018-07-14T15:44:20 Z IvanC Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 26 ms 1428 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){
	if(left == right){
		seg[pos] = node(1 - tabela[1][left],1 - tabela[2][left]);
	}
	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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 10 ms 376 KB Output is correct
3 Correct 26 ms 424 KB Output is correct
4 Correct 24 ms 552 KB Output is correct
5 Correct 10 ms 624 KB Output is correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 3 ms 624 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 22 ms 768 KB Output is correct
12 Correct 18 ms 768 KB Output is correct
13 Correct 13 ms 768 KB Output is correct
14 Correct 10 ms 768 KB Output is correct
15 Correct 3 ms 768 KB Output is correct
16 Correct 3 ms 768 KB Output is correct
17 Correct 2 ms 768 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Runtime error 4 ms 1428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Runtime error 4 ms 1428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 10 ms 376 KB Output is correct
3 Correct 26 ms 424 KB Output is correct
4 Correct 24 ms 552 KB Output is correct
5 Correct 10 ms 624 KB Output is correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 3 ms 624 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 22 ms 768 KB Output is correct
12 Correct 18 ms 768 KB Output is correct
13 Correct 13 ms 768 KB Output is correct
14 Correct 10 ms 768 KB Output is correct
15 Correct 3 ms 768 KB Output is correct
16 Correct 3 ms 768 KB Output is correct
17 Correct 2 ms 768 KB Output is correct
18 Runtime error 3 ms 1428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 10 ms 376 KB Output is correct
3 Correct 26 ms 424 KB Output is correct
4 Correct 24 ms 552 KB Output is correct
5 Correct 10 ms 624 KB Output is correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 3 ms 624 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 22 ms 768 KB Output is correct
12 Correct 18 ms 768 KB Output is correct
13 Correct 13 ms 768 KB Output is correct
14 Correct 10 ms 768 KB Output is correct
15 Correct 3 ms 768 KB Output is correct
16 Correct 3 ms 768 KB Output is correct
17 Correct 2 ms 768 KB Output is correct
18 Runtime error 3 ms 1428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -