oj.uz

Submission #68626

# Submission time Handle Problem Language Result Execution time Memory
68626 2018-08-17T17:00:07 Z KLPP Land of the Rainbow Gold (APIO17_rainbow) C++14
0 / 100
 57 ms 1388 KB 
#include "rainbow.h"
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
bool table[500][500];
int r,c;
int CC[200000][2];
int STm[200000][32][2];
int STM[200000][32][2];
void init(int R, int C, int sr, int sc, int M, char *S) {
	
	r=R;
	c=C;
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++)table[i][j]=1;
	}
	int x,y;
	x=sr-1;
	y=sc-1;
	table[x][y]=0;
	for(int i=0;i<M;i++){
		char c=S[i];
		if(c=='N')x--;
		if(c=='S')x++;
		if(c=='E')y++;
		if(c=='W')y--;
		table[x][y]=0;
	}
	/*for(int i=0;i<r;i++){
		for(int j=0;j<c;j++)cout<<table[i][j];
		cout<<endl;
	}*/
	if(r==2){
		int n=c;
		int color=0;	
		for(int i=0;i<n;i++){
			if(table[0][i]){//cout<<i<<endl;
				if(i>0 && table[0][i-1])CC[i][0]=CC[i-1][0];
				else CC[i][0]=color++;
			}else CC[i][0]=-1;
			//cout<<CC[i][0]<<" ";
		}//cout<<endl;
		for(int i=0;i<n;i++){
			if(table[1][i]){
				if(i>0 && table[0][i-1])CC[i][1]=CC[i-1][1];
				else CC[i][1]=color++;
			}else CC[i][1]=-1;
			//cout<<CC[i][1]<<" ";
		}//cout<<endl;
		for(int i=0;i<n;i++){
			STM[i][0][0]=CC[i][0];
			STM[i][0][1]=CC[i][1];
		}
		for(int j=1;j<32;j++){for(int i=0;i<n;i++){
			STM[i][j][0]=max(STM[i][j-1][0],STM[min(n-1,i+(1<<(j-1)))][j-1][0]);
			STM[i][j][1]=max(STM[i][j-1][1],STM[min(n-1,i+(1<<(j-1)))][j-1][1]);
			}
		}
		for(int i=0;i<n;i++){
			STm[i][0][0]=CC[i][0];
			STm[i][0][1]=CC[i][1];
			if(CC[i][0]==-1)STm[i][0][0]=n+1;
			if(CC[i][1]==-1)STm[i][0][1]=n+1;
		}
		for(int j=1;j<32;j++){
			for(int i=0;i<n;i++){
			STm[i][j][0]=min(STm[i][j-1][0],STm[min(n-1,i+(1<<(j-1)))][j-1][0]);
			STm[i][j][1]=min(STm[i][j-1][1],STm[min(n-1,i+(1<<(j-1)))][j-1][1]);
			}
		}
	}
}

int colour(int ar, int ac, int br, int bc){
	ar--;
	ac--;
	br--;
	bc--;
	if(r!=2){
	bool visited[r][c];
	for(int x=ar;x<=br;x++){
		for(int y=ac;y<=bc;y++){
			visited[x][y]=false;
		}
	}
	int CC=0;
	for(int x=ar;x<=br;x++){
		for(int y=ac;y<=bc;y++){
			if(!visited[x][y] && table[x][y]){
			queue<pii>q;
			q.push(pii(x,y));
			while(!q.empty()){
				pii p=q.front();q.pop();
				if(ar<=p.first && p.first<=br && ac<=p.second && p.second<=bc && !visited[p.first][p.second] && table[p.first][p.second]){
					visited[p.first][p.second]=true;
					q.push(pii(p.first-1,p.second));
					q.push(pii(p.first+1,p.second));
					q.push(pii(p.first,p.second+1));
					q.push(pii(p.first,p.second-1));
				}
			}
			CC++;
			}
		}
	}
	return CC;
	}
	int pow=30;
	while((1<<pow)>bc-ac+1){
		pow--;
	}
	if(ar==br){
		int maximo=max(STM[ac][pow][ar],STM[bc-(1<<pow)+1][pow][ar]);
		int minimo=min(STm[ac][pow][ar],STm[bc-(1<<pow)+1][pow][ar]);
		//cout<<maximo<<" "<<minimo<<" "<<pow<<endl;
		if(maximo==-1)return 0;
		return maximo-minimo+1;
	}
	int CC=0;
	for(int a=ar;a<=br;a++){
		int maximo=max(STM[ac][pow][a],STM[bc-(1<<pow)+1][pow][a]);
		int minimo=min(STm[ac][pow][a],STm[bc-(1<<pow)+1][pow][a]);
		if(maximo>=0)CC+=maximo-minimo+1;
	}
	return CC;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 248 KB Output is correct
2 Correct 17 ms 484 KB Output is correct
3 Correct 48 ms 580 KB Output is correct
4 Correct 57 ms 580 KB Output is correct
5 Correct 15 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 3 ms 644 KB Output is correct
8 Correct 3 ms 644 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 41 ms 724 KB Output is correct
12 Correct 30 ms 724 KB Output is correct
13 Correct 23 ms 724 KB Output is correct
14 Correct 34 ms 724 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 2 ms 724 KB Output is correct
17 Incorrect 2 ms 724 KB Output isn't correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Incorrect 2 ms 724 KB Output isn't correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Runtime error 44 ms 1388 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 6 ms 248 KB Output is correct
2 Correct 17 ms 484 KB Output is correct
3 Correct 48 ms 580 KB Output is correct
4 Correct 57 ms 580 KB Output is correct
5 Correct 15 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 3 ms 644 KB Output is correct
8 Correct 3 ms 644 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 41 ms 724 KB Output is correct
12 Correct 30 ms 724 KB Output is correct
13 Correct 23 ms 724 KB Output is correct
14 Correct 34 ms 724 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 2 ms 724 KB Output is correct
17 Incorrect 2 ms 724 KB Output isn't correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 248 KB Output is correct
2 Correct 17 ms 484 KB Output is correct
3 Correct 48 ms 580 KB Output is correct
4 Correct 57 ms 580 KB Output is correct
5 Correct 15 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 3 ms 644 KB Output is correct
8 Correct 3 ms 644 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 41 ms 724 KB Output is correct
12 Correct 30 ms 724 KB Output is correct
13 Correct 23 ms 724 KB Output is correct
14 Correct 34 ms 724 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 2 ms 724 KB Output is correct
17 Incorrect 2 ms 724 KB Output isn't correct