oj.uz

Submission #101733

# Submission time Handle Problem Language Result Execution time Memory
101733 2019-03-19T16:34:46 Z Bruteforceman Land of the Rainbow Gold (APIO17_rainbow) C++11
0 / 100
 3000 ms 91536 KB 
#include "rainbow.h"
#include "bits/stdc++.h"
using namespace std;

int N, M;
typedef pair <int, int> pii;

struct Container {
	vector <int> t[200010 * 4];
	vector <pii> u;
	void insert(int x, int y, int c, int b, int e) {
		if(b == e) {
			t[c].emplace_back(y);
			return ;
		}
		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		if(x <= m) insert(x, y, l, b, m);
		else insert(x, y, r, m + 1, e);
	}
	void build(int c, int b, int e) {
		if(b == e) {
			sort(t[c].begin(), t[c].end());
			return ;
		}
		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		build(l, b, m);
		build(r, m + 1, e);
		merge(t[l].begin(), t[l].end(), t[r].begin(), t[r].end(), back_inserter(t[c]));
	}
	int count(int x, int y, int p, int q, int c, int b, int e) {
		if(x <= b && e <= y) {
			return upper_bound(t[c].begin(), t[c].end(), q) - lower_bound(t[c].begin(), t[c].end(), p);
		}
		if(y < b || e < x) return 0;
		int l = c << 1;
		int r = l + 1;
		int m = (b + e) >> 1;
		return count(x, y, p, q, l, b, m) + count(x, y, p, q, r, m + 1, e);
	}
	int count(int x, int y, int p, int q) {
		int ans = 0;
		for(auto i : u) {
			if(x <= i.first && i.first <= y) {
				if(p <= i.second && i.second <= q) {
					++ans;
				}
			}
		}
		return ans;
	}
	void insert(int x, int y) {
		u.emplace_back(x, y);
		return ;
		// insert(x, y, 1, 1, N);
	}
	void build() {
		// build(1, 1, N);
	}
} E1, E2, V, F;
int lx, rx, ly, ry;

void init(int R, int C, int sr, int sc, int len, char *S) {
	N = R;
	M = C;
	vector <pii> u;
	u.emplace_back(sr, sc);
	// int len = strlen();
	for(int i = 0; i < len; i++) {
		if(S[i] == 'N') --sr;
		else if (S[i] == 'S') ++sr;
		else if (S[i] == 'W') --sc;
		else ++sc;  
		u.emplace_back(sr, sc);
	}
	lx = N, ly = M;
	rx = 1, ry = 1;
	for(auto i : u) {
		lx = min(lx, i.first);
		ly = min(ly, i.second);
		rx = max(rx, i.first);
		ry = max(ry, i.second);
	}	
	// cout << lx << ' ' << rx << ' ' << ly << ' ' << ry << endl;
	// for(auto i : u) {
	// 	cout << i.first << ' ' << i.second << endl;
	// }
	set <pii> s;
	for(auto i : u) {
		s.emplace(i.first, i.second);
		s.emplace(i.first - 1, i.second);
		s.emplace(i.first, i.second - 1);
		s.emplace(i.first - 1, i.second - 1);
	}
	for(auto i : s) {
		if(0 < i.first && 0 < i.second) {
			F.insert(i.first, i.second);
		}
	}
	s.clear();
	
	for(auto i : u) {
		s.emplace(i.first - 1, i.second);
		s.emplace(i.first, i.second);
	}
	for(auto i : s) {
		if(0 < i.first && 0 < i.second) {
			E1.insert(i.first, i.second);
		}
	}
	s.clear();
	
	for(auto i : u) {
		s.emplace(i.first, i.second - 1);
		s.emplace(i.first, i.second);
	}
	for(auto i : s) {
		if(0 < i.first && 0 < i.second) {
			E2.insert(i.first, i.second);
		}
	}
	s.clear();
	
	for(auto i : u) {
		s.emplace(i.first, i.second);
	}
	for(auto i : s) {
		V.insert(i.first, i.second);
	}
	s.clear();

	F.build();
	V.build();
	E1.build();
	E2.build();
}

int colour(int ar, int ac, int br, int bc) {
	if(ar < lx && rx < br) {
		if(ac < ly && ry < bc) {
			return 1;
		}
	}
	long long cnt = 0;
	int row = br - ar + 1;
	int col = bc - ac + 1;

	long long e = 0;
	e += 1LL * (row - 1) * col;
	e += 1LL * row * (col - 1);
	e -= E1.count(ar, br - 1, ac, bc);
	e -= E2.count(ar, br, ac, bc - 1);

	long long v = 0;   
	v += 1LL * row * col;
	v -= V.count(ar, br, ac, bc);

	long long f = 1;
	f += 1LL * (row - 1) * (col - 1);
	f -= F.count(ar, br - 1, ac, bc - 1);
	cnt = v - e + f - 1;
    return cnt;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 75512 KB Output is correct
2 Correct 81 ms 75644 KB Output is correct
3 Incorrect 86 ms 75512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 75480 KB Output is correct
2 Correct 63 ms 75512 KB Output is correct
3 Execution timed out 3038 ms 83900 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 75492 KB Output is correct
2 Correct 372 ms 91536 KB Output is correct
3 Correct 346 ms 91272 KB Output is correct
4 Correct 277 ms 89252 KB Output is correct
5 Correct 274 ms 86072 KB Output is correct
6 Correct 175 ms 79004 KB Output is correct
7 Incorrect 246 ms 81644 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 75512 KB Output is correct
2 Correct 81 ms 75644 KB Output is correct
3 Incorrect 86 ms 75512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 75512 KB Output is correct
2 Correct 81 ms 75644 KB Output is correct
3 Incorrect 86 ms 75512 KB Output isn't correct
4 Halted 0 ms 0 KB -