oj.uz

Submission #263642

# Submission time Handle Problem Language Result Execution time Memory
263642 2020-08-13T23:33:24 Z amoo_safar Land of the Rainbow Gold (APIO17_rainbow) C++14
23 / 100
 636 ms 76604 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;
}

void DFS(int u){
	int X = Fr[u].F;
	int Y = Fr[u].S;
	mark[u] = 1;
	int adj;
	for(int x = X - 1; x <= X + 1; x++)
		for(int y = Y - 1; y <= Y + 1; y++){
			adj = ID({x, 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 34 ms 25600 KB Output is correct
3 Correct 27 ms 25472 KB Output is correct
4 Correct 26 ms 25472 KB Output is correct
5 Correct 31 ms 25600 KB Output is correct
6 Correct 24 ms 25344 KB Output is correct
7 Correct 24 ms 25344 KB Output is correct
8 Correct 24 ms 25344 KB Output is correct
9 Correct 26 ms 25400 KB Output is correct
10 Correct 30 ms 25472 KB Output is correct
11 Correct 26 ms 25472 KB Output is correct
12 Correct 34 ms 25600 KB Output is correct
13 Correct 32 ms 25728 KB Output is correct
14 Correct 35 ms 26112 KB Output is correct
15 Correct 24 ms 25336 KB Output is correct
16 Correct 29 ms 25464 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 29 ms 25464 KB Output is correct
2 Correct 24 ms 25344 KB Output is correct
3 Correct 351 ms 43520 KB Output is correct
4 Correct 584 ms 56272 KB Output is correct
5 Correct 613 ms 58944 KB Output is correct
6 Correct 534 ms 49236 KB Output is correct
7 Correct 636 ms 64860 KB Output is correct
8 Correct 108 ms 26900 KB Output is correct
9 Correct 555 ms 56124 KB Output is correct
10 Correct 633 ms 59012 KB Output is correct
11 Correct 501 ms 49236 KB Output is correct
12 Correct 432 ms 53216 KB Output is correct
13 Correct 480 ms 56136 KB Output is correct
14 Correct 539 ms 58940 KB Output is correct
15 Correct 450 ms 49236 KB Output is correct
16 Correct 408 ms 46436 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25336 KB Output is correct
2 Correct 348 ms 55176 KB Output is correct
3 Correct 498 ms 55184 KB Output is correct
4 Correct 560 ms 76604 KB Output is correct
5 Correct 350 ms 47824 KB Output is correct
6 Correct 105 ms 29164 KB Output is correct
7 Incorrect 165 ms 31208 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25472 KB Output is correct
2 Correct 34 ms 25600 KB Output is correct
3 Correct 27 ms 25472 KB Output is correct
4 Correct 26 ms 25472 KB Output is correct
5 Correct 31 ms 25600 KB Output is correct
6 Correct 24 ms 25344 KB Output is correct
7 Correct 24 ms 25344 KB Output is correct
8 Correct 24 ms 25344 KB Output is correct
9 Correct 26 ms 25400 KB Output is correct
10 Correct 30 ms 25472 KB Output is correct
11 Correct 26 ms 25472 KB Output is correct
12 Correct 34 ms 25600 KB Output is correct
13 Correct 32 ms 25728 KB Output is correct
14 Correct 35 ms 26112 KB Output is correct
15 Correct 24 ms 25336 KB Output is correct
16 Correct 29 ms 25464 KB Output is correct
17 Correct 24 ms 25344 KB Output is correct
18 Correct 484 ms 39368 KB Output is correct
19 Correct 143 ms 29316 KB Output is correct
20 Correct 122 ms 29048 KB Output is correct
21 Correct 128 ms 29088 KB Output is correct
22 Correct 138 ms 29048 KB Output is correct
23 Correct 131 ms 29300 KB Output is correct
24 Incorrect 151 ms 29048 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25472 KB Output is correct
2 Correct 34 ms 25600 KB Output is correct
3 Correct 27 ms 25472 KB Output is correct
4 Correct 26 ms 25472 KB Output is correct
5 Correct 31 ms 25600 KB Output is correct
6 Correct 24 ms 25344 KB Output is correct
7 Correct 24 ms 25344 KB Output is correct
8 Correct 24 ms 25344 KB Output is correct
9 Correct 26 ms 25400 KB Output is correct
10 Correct 30 ms 25472 KB Output is correct
11 Correct 26 ms 25472 KB Output is correct
12 Correct 34 ms 25600 KB Output is correct
13 Correct 32 ms 25728 KB Output is correct
14 Correct 35 ms 26112 KB Output is correct
15 Correct 24 ms 25336 KB Output is correct
16 Correct 29 ms 25464 KB Output is correct
17 Correct 24 ms 25344 KB Output is correct
18 Correct 484 ms 39368 KB Output is correct
19 Correct 143 ms 29316 KB Output is correct
20 Correct 122 ms 29048 KB Output is correct
21 Correct 128 ms 29088 KB Output is correct
22 Correct 138 ms 29048 KB Output is correct
23 Correct 131 ms 29300 KB Output is correct
24 Incorrect 151 ms 29048 KB Output isn't correct
25 Halted 0 ms 0 KB -