oj.uz

Submission #263643

# Submission time Handle Problem Language Result Execution time Memory
263643 2020-08-13T23:37:23 Z amoo_safar Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 735 ms 73916 KB 
// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define F first
#define S second
#define pb push_back

#ifndef safar
#include "rainbow.h"
#endif

using namespace std;

const int N = 2e5 + 10;

typedef pair<int, int> pii;

template<typename T>
void Unique(vector<T> &V){
	sort(all(V));
	V.resize(unique(all(V)) - V.begin());
}


int R, C;
vector<pii> Riv, P;

pii corner[] = {{0, 0}, {0, -1}, {-1, -1}, {-1, 0}};

bool Exist(pii X){
	return X == *lower_bound(all(Riv), X);
}

vector<int> RE[N], CE[N];

vector<pii> Fen[N];
vector<int> PS[N];

void Add(pii P, int d){
	//cerr << "# " << P.F << " " << P.S << " : " << d << '\n';
	for(int idx = P.F; idx < N; idx += idx & (-idx))
		Fen[idx].pb({P.S, d});
}
////////////////
int com;
const int N2 = 3*N;
vector<pii> Fr;
int mark[N2];

int ID(pii X){
	int x = lower_bound(all(Fr), X) - Fr.begin();
	if(x == (int)Fr.size()) return -1;
	if(Fr[x] != X) return -1;
	return x;
}

pii side[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

void DFS(int u){
	int X = Fr[u].F;
	int Y = Fr[u].S;
	mark[u] = 1;
	int adj;
	for(auto [x, y] : side){
		adj = ID({X + x, Y + y});
		if(adj == -1 || mark[adj]) continue;
		DFS(adj);
	}

}

////////////////
int mxx = -1, mxy = -1, mnx = 1e9, mny = 1e9;

void init(int Ri, int Ci, int sr, int sc, int m, char *s){
	R = Ri; C = Ci;

	Riv.resize(m + 1);
	Riv[0] = {sr, sc};
	for(int i = 1; i <= m; i++){
		if(s[i - 1] == 'N') sr --;
		if(s[i - 1] == 'S') sr ++;
		if(s[i - 1] == 'W') sc --;
		if(s[i - 1] == 'E') sc ++;
		Riv[i] = {sr, sc};
	}
	Unique(Riv);
	
	for(auto &X : Riv)
		for(auto &del : corner)
			if(min(X.F + del.F, X.S + del.S) > 0)
				P.pb({X.F + del.F, X.S + del.S});
	
	for(auto &X : Riv)
		for(int x = X.F - 1; x <= X.F + 1; x++)
			for(int y = X.S - 1; y <= X.S + 1; y++)
				if(!Exist({x, y}))
					Fr.pb({x, y});

	Unique(P);
	//for(auto X : Riv) cerr << X.F << ' ' << X.S << '\n';
	Riv.pb({R + R, C + 2});

	for(auto &X : Riv){
		if(X.F == R + R) break;
		
		for(int x = X.F - 1; x <= X.F + 1; x++)
			for(int y = X.S - 1; y <= X.S + 1; y++)
				if(!Exist({x, y}))
					Fr.pb({x, y});		

		mxx = max(mxx, X.F);
		mnx = min(mnx, X.F);
		mxy = max(mxy, X.S);
		mny = min(mny, X.S);

		if(!Exist({X.F, X.S - 1}))
			RE[X.F].pb(X.S - 1);
		
		if(!Exist({X.F, X.S + 1}))
			RE[X.F].pb(X.S);
		
		if(!Exist({X.F - 1, X.S}))
			CE[X.S].pb(X.F - 1);
		
		if(!Exist({X.F + 1, X.S}))
			CE[X.S].pb(X.F);
	}

	Unique(Fr);

	for(int i = 0; i < (int) Fr.size(); i++){
		if(!mark[i]){
			DFS(i);
			com ++;
		}
	}
	//cerr << "## " << com << '\n';



	int cnt;
	vector<int> ex;
	for(auto X : P){
		cnt = 0;
		int po = 0;
		ex.clear();
		for(auto &del : corner){
			if(Exist({X.F - del.F, X.S - del.S})){
				cnt ++;
				ex.pb(po);
			}
			po ++;
		}

		if(cnt & 1)
			Add(X, cnt == 1 ? -1 : 1);
		if(cnt == 2){
			if(ex[1] - ex[0] == 2){
				Add(X, 2);
			}
		}
	}

	for(int i = 1; i < N; i++){
		sort(all(Fen[i]));
		PS[i].resize(Fen[i].size() + 1, 0);
		for(int j = 1; j <= (int) Fen[i].size(); j++){
			PS[i][j] = PS[i][j - 1] + Fen[i][j - 1].S;
		}
	}
}

int Get(int x, int y){
	int res = 0;
	for(; x; x -= x & (-x)){
		res += PS[x][upper_bound(all(Fen[x]), pii(y, 5)) - Fen[x].begin()];
	}
	return res;
}

int colour(int ar, int ac, int br, int bc){
	if((ar < mnx) && (ac < mny) && (mxx < br) && (mxy < bc)){
		//assert(false);
		return com;
	}
	int sum = 0;
	if(!Exist({ar, ac})) sum ++;
	if(!Exist({ar, bc})) sum ++;
	if(!Exist({br, ac})) sum ++;
	if(!Exist({br, bc})) sum ++;

	//cerr << "1 " << sum << '\n';

	if(ar < br && ac < bc){
		sum += Get(br - 1, bc - 1);
		//cerr << "1.1 " << sum << '\n';
		sum -= Get(ar - 1, bc - 1);
		sum -= Get(br - 1, ac - 1);
		sum += Get(ar - 1, ac - 1);
	}
	//cerr << "2 " << sum << '\n';

	sum += lower_bound(all(RE[ar]), bc) - upper_bound(all(RE[ar]), ac - 1);
	sum += lower_bound(all(RE[br]), bc) - upper_bound(all(RE[br]), ac - 1);
	
	sum += lower_bound(all(CE[ac]), br) - upper_bound(all(CE[ac]), ar - 1);
	sum += lower_bound(all(CE[bc]), br) - upper_bound(all(CE[bc]), ar - 1);
	//cerr << "! " << sum << '\n';
	assert(sum % 4 == 0);
	return sum / 4;
}


#ifdef safar
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	init(6, 6, 2, 2, 8, "ESNW");
	//cerr << "# " << Get(6, 4) << '\n';
	//cerr << Get(3, 2) << '\n';
	
	cout << colour(1, 1, 6, 6) << '\n';
	//cout << colour(3, 2, 4, 4) << '\n';
	//cout << colour(5, 3, 6, 4) << '\n';
	//cout << colour(1, 2, 5, 3) << '\n';
	//cout << colour(1, 1, 6, 4) << '\n';
	return 0;
}
#endif

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25472 KB Output is correct
2 Correct 28 ms 25564 KB Output is correct
3 Correct 25 ms 25472 KB Output is correct
4 Correct 26 ms 25464 KB Output is correct
5 Correct 33 ms 25464 KB Output is correct
6 Correct 24 ms 25360 KB Output is correct
7 Correct 24 ms 25424 KB Output is correct
8 Correct 24 ms 25340 KB Output is correct
9 Correct 24 ms 25344 KB Output is correct
10 Correct 28 ms 25344 KB Output is correct
11 Correct 26 ms 25472 KB Output is correct
12 Correct 34 ms 25592 KB Output is correct
13 Correct 32 ms 25600 KB Output is correct
14 Correct 34 ms 26112 KB Output is correct
15 Correct 24 ms 25344 KB Output is correct
16 Correct 28 ms 25336 KB Output is correct
17 Correct 24 ms 25344 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 25336 KB Output is correct
2 Correct 24 ms 25344 KB Output is correct
3 Correct 311 ms 39804 KB Output is correct
4 Correct 504 ms 50108 KB Output is correct
5 Correct 551 ms 53692 KB Output is correct
6 Correct 448 ms 46040 KB Output is correct
7 Correct 601 ms 61700 KB Output is correct
8 Correct 108 ms 27000 KB Output is correct
9 Correct 492 ms 50080 KB Output is correct
10 Correct 543 ms 53564 KB Output is correct
11 Correct 496 ms 46036 KB Output is correct
12 Correct 382 ms 47456 KB Output is correct
13 Correct 423 ms 50248 KB Output is correct
14 Correct 470 ms 53564 KB Output is correct
15 Correct 401 ms 46264 KB Output is correct
16 Correct 368 ms 42196 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25344 KB Output is correct
2 Correct 312 ms 48936 KB Output is correct
3 Correct 456 ms 49144 KB Output is correct
4 Correct 488 ms 70204 KB Output is correct
5 Correct 299 ms 43344 KB Output is correct
6 Correct 99 ms 29036 KB Output is correct
7 Correct 160 ms 31080 KB Output is correct
8 Correct 330 ms 44372 KB Output is correct
9 Correct 313 ms 42476 KB Output is correct
10 Correct 99 ms 28664 KB Output is correct
11 Correct 225 ms 36820 KB Output is correct
12 Correct 302 ms 49064 KB Output is correct
13 Correct 451 ms 49216 KB Output is correct
14 Correct 487 ms 70332 KB Output is correct
15 Correct 304 ms 43216 KB Output is correct
16 Correct 84 ms 28268 KB Output is correct
17 Correct 160 ms 31976 KB Output is correct
18 Correct 383 ms 43684 KB Output is correct
19 Correct 371 ms 48344 KB Output is correct
20 Correct 369 ms 48312 KB Output is correct
21 Correct 345 ms 44368 KB Output is correct
22 Correct 325 ms 42328 KB Output is correct
23 Correct 105 ms 28660 KB Output is correct
24 Correct 230 ms 36972 KB Output is correct
25 Correct 301 ms 49064 KB Output is correct
26 Correct 467 ms 49064 KB Output is correct
27 Correct 488 ms 70332 KB Output is correct
28 Correct 301 ms 43344 KB Output is correct
29 Correct 86 ms 28396 KB Output is correct
30 Correct 163 ms 31936 KB Output is correct
31 Correct 371 ms 43824 KB Output is correct
32 Correct 365 ms 48316 KB Output is correct
33 Correct 364 ms 48340 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25472 KB Output is correct
2 Correct 28 ms 25564 KB Output is correct
3 Correct 25 ms 25472 KB Output is correct
4 Correct 26 ms 25464 KB Output is correct
5 Correct 33 ms 25464 KB Output is correct
6 Correct 24 ms 25360 KB Output is correct
7 Correct 24 ms 25424 KB Output is correct
8 Correct 24 ms 25340 KB Output is correct
9 Correct 24 ms 25344 KB Output is correct
10 Correct 28 ms 25344 KB Output is correct
11 Correct 26 ms 25472 KB Output is correct
12 Correct 34 ms 25592 KB Output is correct
13 Correct 32 ms 25600 KB Output is correct
14 Correct 34 ms 26112 KB Output is correct
15 Correct 24 ms 25344 KB Output is correct
16 Correct 28 ms 25336 KB Output is correct
17 Correct 24 ms 25344 KB Output is correct
18 Correct 447 ms 34404 KB Output is correct
19 Correct 140 ms 26628 KB Output is correct
20 Correct 123 ms 26104 KB Output is correct
21 Correct 125 ms 26232 KB Output is correct
22 Correct 134 ms 26360 KB Output is correct
23 Correct 128 ms 26484 KB Output is correct
24 Correct 147 ms 26232 KB Output is correct
25 Correct 158 ms 29084 KB Output is correct
26 Correct 145 ms 29176 KB Output is correct
27 Correct 314 ms 34404 KB Output is correct
28 Correct 254 ms 33232 KB Output is correct
29 Correct 314 ms 35560 KB Output is correct
30 Correct 534 ms 47316 KB Output is correct
31 Correct 30 ms 25464 KB Output is correct
32 Correct 505 ms 45664 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25472 KB Output is correct
2 Correct 28 ms 25564 KB Output is correct
3 Correct 25 ms 25472 KB Output is correct
4 Correct 26 ms 25464 KB Output is correct
5 Correct 33 ms 25464 KB Output is correct
6 Correct 24 ms 25360 KB Output is correct
7 Correct 24 ms 25424 KB Output is correct
8 Correct 24 ms 25340 KB Output is correct
9 Correct 24 ms 25344 KB Output is correct
10 Correct 28 ms 25344 KB Output is correct
11 Correct 26 ms 25472 KB Output is correct
12 Correct 34 ms 25592 KB Output is correct
13 Correct 32 ms 25600 KB Output is correct
14 Correct 34 ms 26112 KB Output is correct
15 Correct 24 ms 25344 KB Output is correct
16 Correct 28 ms 25336 KB Output is correct
17 Correct 24 ms 25344 KB Output is correct
18 Correct 447 ms 34404 KB Output is correct
19 Correct 140 ms 26628 KB Output is correct
20 Correct 123 ms 26104 KB Output is correct
21 Correct 125 ms 26232 KB Output is correct
22 Correct 134 ms 26360 KB Output is correct
23 Correct 128 ms 26484 KB Output is correct
24 Correct 147 ms 26232 KB Output is correct
25 Correct 158 ms 29084 KB Output is correct
26 Correct 145 ms 29176 KB Output is correct
27 Correct 314 ms 34404 KB Output is correct
28 Correct 254 ms 33232 KB Output is correct
29 Correct 314 ms 35560 KB Output is correct
30 Correct 534 ms 47316 KB Output is correct
31 Correct 30 ms 25464 KB Output is correct
32 Correct 505 ms 45664 KB Output is correct
33 Correct 312 ms 48936 KB Output is correct
34 Correct 456 ms 49144 KB Output is correct
35 Correct 488 ms 70204 KB Output is correct
36 Correct 299 ms 43344 KB Output is correct
37 Correct 99 ms 29036 KB Output is correct
38 Correct 160 ms 31080 KB Output is correct
39 Correct 330 ms 44372 KB Output is correct
40 Correct 313 ms 42476 KB Output is correct
41 Correct 99 ms 28664 KB Output is correct
42 Correct 225 ms 36820 KB Output is correct
43 Correct 302 ms 49064 KB Output is correct
44 Correct 451 ms 49216 KB Output is correct
45 Correct 487 ms 70332 KB Output is correct
46 Correct 304 ms 43216 KB Output is correct
47 Correct 84 ms 28268 KB Output is correct
48 Correct 160 ms 31976 KB Output is correct
49 Correct 383 ms 43684 KB Output is correct
50 Correct 371 ms 48344 KB Output is correct
51 Correct 369 ms 48312 KB Output is correct
52 Correct 345 ms 44368 KB Output is correct
53 Correct 325 ms 42328 KB Output is correct
54 Correct 105 ms 28660 KB Output is correct
55 Correct 230 ms 36972 KB Output is correct
56 Correct 301 ms 49064 KB Output is correct
57 Correct 467 ms 49064 KB Output is correct
58 Correct 488 ms 70332 KB Output is correct
59 Correct 301 ms 43344 KB Output is correct
60 Correct 86 ms 28396 KB Output is correct
61 Correct 163 ms 31936 KB Output is correct
62 Correct 371 ms 43824 KB Output is correct
63 Correct 365 ms 48316 KB Output is correct
64 Correct 364 ms 48340 KB Output is correct
65 Correct 546 ms 47696 KB Output is correct
66 Correct 537 ms 45908 KB Output is correct
67 Correct 278 ms 32120 KB Output is correct
68 Correct 400 ms 40276 KB Output is correct
69 Correct 473 ms 52668 KB Output is correct
70 Correct 637 ms 52600 KB Output is correct
71 Correct 735 ms 73916 KB Output is correct
72 Correct 471 ms 46800 KB Output is correct
73 Correct 239 ms 31852 KB Output is correct
74 Correct 323 ms 35432 KB Output is correct
75 Correct 540 ms 47420 KB Output is correct
76 Correct 562 ms 51904 KB Output is correct
77 Correct 527 ms 51760 KB Output is correct
78 Correct 311 ms 39804 KB Output is correct
79 Correct 504 ms 50108 KB Output is correct
80 Correct 551 ms 53692 KB Output is correct
81 Correct 448 ms 46040 KB Output is correct
82 Correct 601 ms 61700 KB Output is correct
83 Correct 108 ms 27000 KB Output is correct
84 Correct 492 ms 50080 KB Output is correct
85 Correct 543 ms 53564 KB Output is correct
86 Correct 496 ms 46036 KB Output is correct
87 Correct 382 ms 47456 KB Output is correct
88 Correct 423 ms 50248 KB Output is correct
89 Correct 470 ms 53564 KB Output is correct
90 Correct 401 ms 46264 KB Output is correct
91 Correct 368 ms 42196 KB Output is correct