oj.uz

Submission #263576

# Submission time Handle Problem Language Result Execution time Memory
263576 2020-08-13T19:43:52 Z amoo_safar Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 441 ms 56908 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 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});
	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;
		
		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);
	}

	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 1;
	}
	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, 4, 3, 3, 9, "NWESSWEWS");
	//cerr << "# " << Get(6, 4) << '\n';
	//cerr << Get(3, 2) << '\n';
	
	cout << colour(2, 3, 2, 3) << '\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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25344 KB Output is correct
2 Correct 28 ms 25472 KB Output is correct
3 Incorrect 31 ms 25472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25344 KB Output is correct
2 Correct 25 ms 25344 KB Output is correct
3 Correct 212 ms 29968 KB Output is correct
4 Correct 270 ms 33760 KB Output is correct
5 Correct 305 ms 37984 KB Output is correct
6 Correct 270 ms 37352 KB Output is correct
7 Correct 441 ms 52584 KB Output is correct
8 Correct 103 ms 27000 KB Output is correct
9 Correct 276 ms 33760 KB Output is correct
10 Correct 307 ms 37976 KB Output is correct
11 Correct 294 ms 37352 KB Output is correct
12 Correct 212 ms 32132 KB Output is correct
13 Correct 197 ms 33736 KB Output is correct
14 Correct 272 ms 37984 KB Output is correct
15 Correct 239 ms 37352 KB Output is correct
16 Correct 225 ms 30396 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25336 KB Output is correct
2 Correct 133 ms 32516 KB Output is correct
3 Correct 122 ms 32456 KB Output is correct
4 Correct 226 ms 56908 KB Output is correct
5 Correct 103 ms 30860 KB Output is correct
6 Correct 66 ms 28396 KB Output is correct
7 Incorrect 94 ms 29888 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 25344 KB Output is correct
2 Correct 28 ms 25472 KB Output is correct
3 Incorrect 31 ms 25472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25344 KB Output is correct
2 Correct 28 ms 25472 KB Output is correct
3 Incorrect 31 ms 25472 KB Output isn't correct
4 Halted 0 ms 0 KB -