oj.uz

Submission #101724

# Submission time Handle Problem Language Result Execution time Memory
101724 2019-03-19T15:44:36 Z Bruteforceman Land of the Rainbow Gold (APIO17_rainbow) C++11
12 / 100
 654 ms 146964 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(lx < ar && br < rx) {
		if(ly < ac && bc < ry) {
			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 Incorrect 69 ms 75512 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 69 ms 75384 KB Output is correct
2 Correct 68 ms 75512 KB Output is correct
3 Correct 362 ms 82804 KB Output is correct
4 Correct 486 ms 88220 KB Output is correct
5 Correct 489 ms 88044 KB Output is correct
6 Correct 412 ms 84988 KB Output is correct
7 Correct 475 ms 84992 KB Output is correct
8 Correct 228 ms 76784 KB Output is correct
9 Correct 419 ms 88144 KB Output is correct
10 Correct 489 ms 88064 KB Output is correct
11 Correct 419 ms 84972 KB Output is correct
12 Correct 397 ms 86936 KB Output is correct
13 Correct 369 ms 88044 KB Output is correct
14 Correct 401 ms 88012 KB Output is correct
15 Correct 388 ms 84972 KB Output is correct
16 Correct 374 ms 84444 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 75384 KB Output is correct
2 Correct 466 ms 122804 KB Output is correct
3 Correct 654 ms 146964 KB Output is correct
4 Correct 508 ms 141164 KB Output is correct
5 Correct 440 ms 123592 KB Output is correct
6 Correct 228 ms 86508 KB Output is correct
7 Incorrect 296 ms 95880 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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