oj.uz

Submission #263480

# Submission time Handle Problem Language Result Execution time Memory
263480 2020-08-13T17:39:03 Z amoo_safar Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 449 ms 60648 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});
}

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;
		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){
	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 63 ms 51320 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 26 ms 25344 KB Output is correct
2 Correct 26 ms 25336 KB Output is correct
3 Correct 192 ms 29968 KB Output is correct
4 Correct 276 ms 33760 KB Output is correct
5 Correct 312 ms 38112 KB Output is correct
6 Correct 276 ms 37416 KB Output is correct
7 Correct 449 ms 52552 KB Output is correct
8 Correct 108 ms 27000 KB Output is correct
9 Correct 285 ms 33732 KB Output is correct
10 Correct 316 ms 37920 KB Output is correct
11 Correct 299 ms 37356 KB Output is correct
12 Correct 210 ms 32164 KB Output is correct
13 Correct 197 ms 33792 KB Output is correct
14 Correct 225 ms 38112 KB Output is correct
15 Correct 223 ms 37480 KB Output is correct
16 Correct 203 ms 30396 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25344 KB Output is correct
2 Correct 133 ms 32588 KB Output is correct
3 Correct 117 ms 32588 KB Output is correct
4 Correct 214 ms 57036 KB Output is correct
5 Correct 102 ms 30944 KB Output is correct
6 Correct 64 ms 28396 KB Output is correct
7 Runtime error 124 ms 60648 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 Runtime error 63 ms 51320 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 63 ms 51320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -