oj.uz

Submission #263545

# Submission time Handle Problem Language Result Execution time Memory
263545 2020-08-13T19:19:11 Z amoo_safar Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 450 ms 60628 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)){
		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 Incorrect 36 ms 25472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25344 KB Output is correct
2 Correct 25 ms 25344 KB Output is correct
3 Correct 216 ms 32900 KB Output is correct
4 Correct 281 ms 36704 KB Output is correct
5 Correct 312 ms 41056 KB Output is correct
6 Correct 279 ms 40300 KB Output is correct
7 Correct 450 ms 55528 KB Output is correct
8 Correct 117 ms 29816 KB Output is correct
9 Correct 292 ms 36576 KB Output is correct
10 Correct 323 ms 40800 KB Output is correct
11 Correct 300 ms 40296 KB Output is correct
12 Correct 200 ms 35024 KB Output is correct
13 Correct 205 ms 36576 KB Output is correct
14 Correct 262 ms 40800 KB Output is correct
15 Correct 231 ms 40280 KB Output is correct
16 Correct 214 ms 33216 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 25336 KB Output is correct
2 Correct 130 ms 32588 KB Output is correct
3 Correct 120 ms 32588 KB Output is correct
4 Correct 224 ms 57036 KB Output is correct
5 Correct 99 ms 30944 KB Output is correct
6 Correct 63 ms 28396 KB Output is correct
7 Runtime error 125 ms 60628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 25472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 25472 KB Output isn't correct
2 Halted 0 ms 0 KB -