oj.uz

Submission #101725

# Submission time Handle Problem Language Result Execution time Memory
101725 2019-03-19T15:46:30 Z Bruteforceman Land of the Rainbow Gold (APIO17_rainbow) C++11
12 / 100
 692 ms 147060 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];
	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) {
		if(x > y || p > q) return 0;
		return count(x, y, p, q, 1, 1, N);
	}
	int insert(int x, int y) {
		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;
}

Compilation message

rainbow.cpp: In member function 'int Container::insert(int, int)':
rainbow.cpp:49:2: warning: no return statement in function returning non-void [-Wreturn-type]
  }
  ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 75512 KB Output is correct
2 Correct 77 ms 75740 KB Output is correct
3 Incorrect 79 ms 75512 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 71 ms 75460 KB Output is correct
2 Correct 66 ms 75512 KB Output is correct
3 Correct 280 ms 82880 KB Output is correct
4 Correct 462 ms 88168 KB Output is correct
5 Correct 441 ms 88044 KB Output is correct
6 Correct 438 ms 84872 KB Output is correct
7 Correct 460 ms 85068 KB Output is correct
8 Correct 229 ms 76656 KB Output is correct
9 Correct 465 ms 88120 KB Output is correct
10 Correct 513 ms 87960 KB Output is correct
11 Correct 345 ms 84844 KB Output is correct
12 Correct 382 ms 86996 KB Output is correct
13 Correct 352 ms 88040 KB Output is correct
14 Correct 417 ms 88016 KB Output is correct
15 Correct 363 ms 84876 KB Output is correct
16 Correct 395 ms 84532 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 75512 KB Output is correct
2 Correct 510 ms 122868 KB Output is correct
3 Correct 605 ms 147060 KB Output is correct
4 Correct 692 ms 140852 KB Output is correct
5 Correct 441 ms 123640 KB Output is correct
6 Correct 223 ms 86480 KB Output is correct
7 Incorrect 310 ms 96096 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 75512 KB Output is correct
2 Correct 77 ms 75740 KB Output is correct
3 Incorrect 79 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 76 ms 75512 KB Output is correct
2 Correct 77 ms 75740 KB Output is correct
3 Incorrect 79 ms 75512 KB Output isn't correct
4 Halted 0 ms 0 KB -