oj.uz

Submission #263483

# Submission time Handle Problem Language Result Execution time Memory
263483 2020-08-13T17:42:19 Z amoo_safar Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 434 ms 56860 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, 0}, {-1, -1}};

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 + 2, C + 2});

	for(auto &X : Riv){
		if(X.F == R + 2) 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;
	for(auto X : P){
		cnt = 0;
		for(auto &del : corner)
			if(Exist({X.F - del.F, X.S - del.S}))
				cnt ++;

		if(cnt & 1)
			Add(X, cnt == 1 ? -1 : 1);
	}

	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, 2)) - Fen[x].begin()];
	}
	return res;
}

int colour(int ar, int ac, int br, int bc){
	if((ar < mnx) && (ac < mny) && (mxx < br) && (mxy < bc)) 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 Runtime error 59 ms 51296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 25344 KB Output is correct
2 Correct 27 ms 25344 KB Output is correct
3 Correct 189 ms 29972 KB Output is correct
4 Correct 275 ms 33844 KB Output is correct
5 Correct 308 ms 38160 KB Output is correct
6 Correct 275 ms 37352 KB Output is correct
7 Correct 434 ms 52560 KB Output is correct
8 Correct 108 ms 27016 KB Output is correct
9 Correct 288 ms 33888 KB Output is correct
10 Correct 307 ms 37984 KB Output is correct
11 Correct 284 ms 37480 KB Output is correct
12 Correct 188 ms 32128 KB Output is correct
13 Correct 195 ms 33760 KB Output is correct
14 Correct 221 ms 38064 KB Output is correct
15 Correct 219 ms 37352 KB Output is correct
16 Correct 204 ms 30396 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 25344 KB Output is correct
2 Correct 138 ms 32460 KB Output is correct
3 Correct 116 ms 32464 KB Output is correct
4 Correct 220 ms 56860 KB Output is correct
5 Correct 98 ms 30816 KB Output is correct
6 Correct 65 ms 28396 KB Output is correct
7 Incorrect 91 ms 30056 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 51296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 51296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -