oj.uz

Submission #250803

# Submission time Handle Problem Language Result Execution time Memory
250803 2020-07-19T07:59:03 Z atoiz Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 3000 ms 136120 KB 
#include "rainbow.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>

using namespace std;

template <typename T>
void normalize(vector<T> &vec)
{
	sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

struct SegmentTree2D
{
	int nx;
	vector<int> valx;
	vector<vector<int>> valy, it;

	int pos(vector<int> &vec, int x) { return int(upper_bound(vec.begin(), vec.end(), x) - vec.begin() - 1); }

	void build(vector<pair<int, int>> vals)
	{
		valx.clear();
		for (auto p : vals) valx.push_back(p.first);
		normalize(valx);
		
		nx = (int) valx.size();
		valy.assign(nx * 2, vector<int>(0));
		it.resize(nx * 2);
		for (auto p : vals) {
			for (int i = pos(valx, p.first) + nx; i >= 1; i >>= 1) valy[i].push_back(p.second);
		}

		for (int i = nx * 2 - 1; i >= 1; --i) {
			normalize(valy[i]);
			int ny = (int) valy[i].size();
			it[i].assign(ny * 2, 0);
		}

		for (auto p : vals) {
			for (int x = pos(valx, p.first) + nx; x >= 1; x >>= 1) {
				int ny = (int) valy[x].size();
				for (int y = pos(valy[x], p.second) + ny; y >= 1; y >>= 1) {
					++it[x][y];
				}
			}
		}
	}

	int get1d(int x, int ly, int ry)
	{
		int ans = 0, ny = (int) valy[x].size();
		for (ly = pos(valy[x], ly - 1) + ny + 1, ry = pos(valy[x], ry) + ny + 1; ly < ry; ly >>= 1, ry >>= 1) {
			if (ly & 1) ans += it[x][ly++];
			if (ry & 1) ans += it[x][--ry];
		}
		return ans;
	}

	int get(int lx, int rx, int ly, int ry)
	{
		int ans = 0;
		for (lx = pos(valx, lx - 1) + nx + 1, rx = pos(valx, rx) + nx + 1; lx < rx; lx >>= 1, rx >>= 1) {
			if (lx & 1) ans += get1d(lx++, ly, ry);
			if (rx & 1) ans += get1d(--rx, ly, ry);
		}
		return ans;
	}
} hr, vt, sq, vx;
int minr, maxr, minc, maxc, fullans;

void init(int R, int C, int sr, int sc, int M, char *S) 
{
	vector<pair<int, int>> vxvec(M + 1);
	vxvec[0] = make_pair(sr, sc);
	minr = maxr = sr, minc = maxc = sc;
	for (int i = 0; i < M; ++i) {
		// cerr << S[i];
		if (S[i] == 'N') --sr;
		else if (S[i] == 'S') ++sr;
		else if (S[i] == 'W') --sc;
		else ++sc;
		minr = min(minr, sr), maxr = max(maxr, sr);
		minc = min(minc, sc), maxc = max(maxc, sc);
		vxvec[i + 1] = make_pair(sr, sc);
	}
	// cerr << endl;
	normalize(vxvec);

	auto hrvec = vxvec, vtvec = vxvec, sqvec = vxvec;
	for (auto p : vxvec) {
		hrvec.emplace_back(p.first, p.second - 1);
		vtvec.emplace_back(p.first - 1, p.second);
		sqvec.emplace_back(p.first, p.second - 1);
		sqvec.emplace_back(p.first - 1, p.second);
		sqvec.emplace_back(p.first - 1, p.second - 1);
	}
	normalize(hrvec), normalize(vtvec), normalize(sqvec);
	hr.build(hrvec), vt.build(vtvec), sq.build(sqvec), vx.build(vxvec);

	set<pair<int, int>> vxset(vxvec.begin(), vxvec.end());
	// for (auto p : vxvec) cerr << p.first << ' ' << p.second << endl; cout << " - " << endl;
	fullans = 0;
	for (auto p : sqvec) {
		int cur = 0;
		if (vxset.find(make_pair(p.first, p.second)) != vxset.end()) ++cur;
		if (vxset.find(make_pair(p.first + 1, p.second)) != vxset.end()) ++cur;
		if (vxset.find(make_pair(p.first, p.second + 1)) != vxset.end()) ++cur;
		if (vxset.find(make_pair(p.first + 1, p.second + 1)) != vxset.end()) ++cur;
		if (cur == 1) ++fullans;
		if (cur == 3) --fullans;
		// cerr << p.first << ' ' << p.second << ": " << cur << endl;
	}
	if (fullans > 4 || fullans % 4) while (true);
	// assert(fullans % 4 == 0);
	// assert(fullans <= 4);
	fullans = 2 - fullans / 4;
	// cerr << fullans << endl;
}

int colour(int ar, int ac, int br, int bc) 
{
	if (ar < minr && maxr < br && ac < minc && maxc < bc) return fullans;

	int64_t hrcnt = 1ll * (br - ar + 1) * (bc - ac) - hr.get(ar, br, ac, bc - 1);
	int64_t vtcnt = 1ll * (br - ar) * (bc - ac + 1) - vt.get(ar, br - 1, ac, bc);
	int64_t sqcnt = 1ll * (br - ar) * (bc - ac) - sq.get(ar, br - 1, ac, bc - 1);
	int64_t vxcnt = 1ll * (br - ar + 1) * (bc - ac + 1) - vx.get(ar, br, ac, bc);
	// cerr << hrcnt << ' ' << vtcnt << ' ' << sqcnt << ' ' << vxcnt << endl;
    return (int) (vxcnt + sqcnt - hrcnt - vtcnt);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 339 ms 18776 KB Output is correct
4 Correct 492 ms 31148 KB Output is correct
5 Correct 485 ms 30656 KB Output is correct
6 Correct 380 ms 23704 KB Output is correct
7 Correct 385 ms 22528 KB Output is correct
8 Correct 76 ms 1152 KB Output is correct
9 Correct 484 ms 31148 KB Output is correct
10 Correct 478 ms 30596 KB Output is correct
11 Correct 408 ms 23708 KB Output is correct
12 Correct 410 ms 29380 KB Output is correct
13 Correct 393 ms 31020 KB Output is correct
14 Correct 395 ms 30656 KB Output is correct
15 Correct 335 ms 23704 KB Output is correct
16 Correct 374 ms 21936 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 281 ms 26120 KB Output is correct
3 Correct 729 ms 136120 KB Output is correct
4 Correct 1090 ms 121136 KB Output is correct
5 Correct 659 ms 94080 KB Output is correct
6 Correct 141 ms 12712 KB Output is correct
7 Execution timed out 3080 ms 22348 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -