oj.uz

Submission #172875

# Submission time Handle Problem Language Result Execution time Memory
172875 2020-01-02T17:25:54 Z dndhk Land of the Rainbow Gold (APIO17_rainbow) C++14
23 / 100
 275 ms 20592 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N1 = 50;
const int MAX_N2 = 200000;
vector<pii> stage;

int N, M;

bool chk[MAX_N1+1][MAX_N1+1];
int type;

bool vst[MAX_N1+1][MAX_N1+1];
pii s, e;

void pro1(){
	type = 1;
	for(int i=0; i<stage.size(); i++){
		chk[stage[i].first][stage[i].second] = true;
	}
}
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

void dfs(int x, int y){
	if(x<s.first || x>e.first || y<s.second || y>e.second)	return;
	if(chk[x][y] || vst[x][y])	return;
	vst[x][y] = true;
	for(int i=0; i<4; i++){
		dfs(x+dx[i], y+dy[i]);
	}
}
bool chk2[3][MAX_N2+1];

struct SEG{
	struct NODE{
		int l, r;
		int sum;
	};
	vector<NODE> seg;
	int SZ, type;
	void add(){
		seg.pb({-1, -1, 0});
	}
	void Init(int x, int y){
		SZ = x;
		type = y;
		add();
		init(0, 1, SZ);
	}
	void init(int idx, int s, int e){
		if(s==e){
			if(type==1){
				seg[idx].sum = chk2[1][s];
			}else if(type==2){
				seg[idx].sum = chk2[2][s];
			}else{
				seg[idx].sum = (chk2[1][s] || chk2[2][s]);
			}
			return;
		}
		seg[idx].l = seg.size(); add();
		seg[idx].r = seg.size(); add();
		init(seg[idx].l, s, (s+e)/2);
		init(seg[idx].r, (s+e)/2+1, e);
		seg[idx].sum = (seg[seg[idx].l].sum + seg[seg[idx].r].sum);
		if(type==1){
			if(chk2[1][(s+e)/2] && chk2[1][(s+e)/2+1])	seg[idx].sum--;
		}else if(type==2){
			if(chk2[2][(s+e)/2] && chk2[2][(s+e)/2+1])	seg[idx].sum--;
		}else{
			if((chk2[1][(s+e)/2] && chk2[1][(s+e)/2+1]) || (chk2[2][(s+e)/2] && chk2[2][(s+e)/2+1])) seg[idx].sum--;
		}
	}
	int Sum(int x, int y){
		return sum(0, 1, SZ, x, y);
	}
	int sum(int idx, int s, int e, int x, int y){
		if(x<=s && e<=y){
			if(type==1){
				if(e!=y && (chk2[1][e] && chk2[1][e+1]))	return seg[idx].sum-1;
				return seg[idx].sum;
			}else if(type==2){
				if(e!=y && (chk2[2][e] && chk2[2][e+1]))	return seg[idx].sum-1;
				return seg[idx].sum;
			}else{
				if(e!=y && ((chk2[1][e] && chk2[1][e+1]) || (chk2[2][e] && chk2[2][e+1])))	return seg[idx].sum-1;
				return seg[idx].sum;
			}
		}else if(x>e || y<s)	return 0;
		return sum(seg[idx].l, s, (s+e)/2, x, y) + sum(seg[idx].r, (s+e)/2+1, e, x, y);
	}
}Seg1, Seg2, Seg3;

void pro2(){
	type = 2;
	for(int i=1; i<=M; i++){
		chk2[1][i] = chk2[2][i] = true;
	}
	for(int i=0; i<stage.size(); i++){
		chk2[stage[i].first][stage[i].second] = false;
	}
	Seg1.Init(M, 1);
	Seg2.Init(M, 2);
	Seg3.Init(M, 3);
}

void pro3(){
	type = 3;
}


void init(int R, int C, int sr, int sc, int l, char *S) {
	N = R; M = C;
	stage.pb({sr, sc});
	for(int i=0; i<l; i++){
		if(S[i]=='N'){
			sr--;
		}else if(S[i]=='E'){
			sc++;
		}else if(S[i]=='W'){
			sc--;
		}else{
			sr++;
		}
		stage.pb({sr, sc});
	}
	if(R==2){
		pro2();
	}else if(R<=50 && C<=50){
		pro1();
	}else{
		pro3();
	}
}

int colour(int ar, int ac, int br, int bc) {
	if(type==1){
		int ans = 0;
		s = {ar, ac}; e = {br, bc};
		for(int i=1; i<=N; i++){
			for(int j=1; j<=M; j++){
				vst[i][j] = false;
			}
		}
		for(int i=ar; i<=br; i++){
			for(int j=ac; j<=bc; j++){
				if(!vst[i][j] && !chk[i][j]){
					dfs(i, j);
					ans++;
				}
			}
		}
		return ans;
	}
	if(type==2){
		if(ar==1 && br==1){
			return Seg1.Sum(ac, bc);
		}else if(ar==2 && br==2){
			return Seg2.Sum(ac, bc);
		}else{
			return Seg3.Sum(ac, bc);
		}
	}
    return 0;
}

Compilation message

rainbow.cpp: In function 'void pro1()':
rainbow.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<stage.size(); i++){
               ~^~~~~~~~~~~~~
rainbow.cpp: In function 'void pro2()':
rainbow.cpp:121:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<stage.size(); i++){
               ~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 11 ms 376 KB Output is correct
3 Correct 20 ms 376 KB Output is correct
4 Correct 20 ms 376 KB Output is correct
5 Correct 10 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 296 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 404 KB Output is correct
11 Correct 18 ms 504 KB Output is correct
12 Correct 16 ms 376 KB Output is correct
13 Correct 12 ms 376 KB Output is correct
14 Correct 9 ms 504 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 219 ms 20228 KB Output is correct
4 Correct 275 ms 20560 KB Output is correct
5 Correct 229 ms 20556 KB Output is correct
6 Correct 222 ms 20420 KB Output is correct
7 Correct 211 ms 20424 KB Output is correct
8 Correct 226 ms 20552 KB Output is correct
9 Correct 230 ms 20592 KB Output is correct
10 Correct 233 ms 20572 KB Output is correct
11 Correct 225 ms 20432 KB Output is correct
12 Correct 105 ms 20424 KB Output is correct
13 Correct 112 ms 20448 KB Output is correct
14 Correct 113 ms 20444 KB Output is correct
15 Correct 108 ms 20564 KB Output is correct
16 Correct 227 ms 20164 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 5 ms 1648 KB Output isn't correct
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 11 ms 376 KB Output is correct
3 Correct 20 ms 376 KB Output is correct
4 Correct 20 ms 376 KB Output is correct
5 Correct 10 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 296 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 404 KB Output is correct
11 Correct 18 ms 504 KB Output is correct
12 Correct 16 ms 376 KB Output is correct
13 Correct 12 ms 376 KB Output is correct
14 Correct 9 ms 504 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Incorrect 68 ms 5012 KB Output isn't correct
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 11 ms 376 KB Output is correct
3 Correct 20 ms 376 KB Output is correct
4 Correct 20 ms 376 KB Output is correct
5 Correct 10 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 296 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 404 KB Output is correct
11 Correct 18 ms 504 KB Output is correct
12 Correct 16 ms 376 KB Output is correct
13 Correct 12 ms 376 KB Output is correct
14 Correct 9 ms 504 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Incorrect 68 ms 5012 KB Output isn't correct
19 Halted 0 ms 0 KB -