oj.uz

Submission #101723

# Submission time Handle Problem Language Result Execution time Memory
101723 2019-03-19T15:33:51 Z Bruteforceman Land of the Rainbow Gold (APIO17_rainbow) C++11
12 / 100
 642 ms 147080 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 M, char *S) {
	N = R;
	M = C;
	vector <pii> u;
	u.emplace_back(sr, sc);
	int len = strlen(S);
	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);
	}
	
	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 88 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 80 ms 75508 KB Output is correct
2 Correct 70 ms 75432 KB Output is correct
3 Correct 340 ms 85700 KB Output is correct
4 Correct 460 ms 90956 KB Output is correct
5 Correct 439 ms 90892 KB Output is correct
6 Correct 365 ms 87884 KB Output is correct
7 Correct 460 ms 87960 KB Output is correct
8 Correct 197 ms 79236 KB Output is correct
9 Correct 451 ms 90916 KB Output is correct
10 Correct 527 ms 90828 KB Output is correct
11 Correct 349 ms 87756 KB Output is correct
12 Correct 391 ms 89748 KB Output is correct
13 Correct 408 ms 90812 KB Output is correct
14 Correct 471 ms 90828 KB Output is correct
15 Correct 419 ms 87804 KB Output is correct
16 Correct 416 ms 87412 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 75448 KB Output is correct
2 Correct 536 ms 122944 KB Output is correct
3 Correct 642 ms 147080 KB Output is correct
4 Correct 510 ms 141164 KB Output is correct
5 Correct 455 ms 123668 KB Output is correct
6 Correct 240 ms 86608 KB Output is correct
7 Incorrect 303 ms 96124 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 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 88 ms 75512 KB Output isn't correct
2 Halted 0 ms 0 KB -