oj.uz

Submission #250836

# Submission time Handle Problem Language Result Execution time Memory
250836 2020-07-19T09:21:21 Z atoiz Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 570 ms 73000 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());
}

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

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

	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);
		}
	}

	void modify(int xx, int yy, int zz)
	{
		for (int x = pos(valx, xx) + nx; x >= 1; x >>= 1) {
			int ny = (int) valy[x].size();
			for (int y = pos(valy[x], yy) + ny; y >= 1; y >>= 1) {
				it[x][y] += zz;
			}
		}
	}

	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;
	}
} st2d;

struct SegmentTree1D
{
	int n;
	vector<int> vals, it;

	void build()
	{
		normalize(vals);
		n = (int) vals.size();
		it.assign(n * 2, 0);
	}

	void modify(int i, int x)
	{
		for (i = pos(vals, i) + n; i >= 1; i >>= 1) {
			it[i] += x;
		}
	}

	int get(int l, int r)
	{
		int ans = 0;
		for (l = pos(vals, l - 1) + n + 1, r = pos(vals, r) + n + 1; l < r; l >>= 1, r >>= 1) {
			if (l & 1) ans += it[l++];
			if (r & 1) ans += it[--r];
		}
		return ans;
	}
};
vector<SegmentTree1D> rowst, colst;
set<pair<int, int>> vxset;

bool ck(int r, int c) { return vxset.find(make_pair(r, c)) == vxset.end(); }

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);
	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;
		vxvec[i + 1] = make_pair(sr, sc);
	}
	// cerr << endl;
	normalize(vxvec);

	auto sqvec = vxvec;
	for (auto p : vxvec) {
		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(sqvec);
	st2d.build(sqvec);

	vxset = set<pair<int, int>>(vxvec.begin(), vxvec.end());
	for (auto p : sqvec) {
		bool b0 = (vxset.find(make_pair(p.first, p.second)) == vxset.end());
		bool b1 = (vxset.find(make_pair(p.first + 1, p.second)) == vxset.end());
		bool b2 = (vxset.find(make_pair(p.first, p.second + 1)) == vxset.end());
		bool b3 = (vxset.find(make_pair(p.first + 1, p.second + 1)) == vxset.end());
		int cnt = (int) b0 + b1 + b2 + b3;
		if (cnt == 3) st2d.modify(p.first, p.second, -1);
		else if (cnt == 1) st2d.modify(p.first, p.second, +1);
		else if (cnt == 2 && ((b0 && b3) || (b1 && b2))) st2d.modify(p.first, p.second, +2);
	}

	rowst.resize(R + 1), colst.resize(C + 1);
	for (auto p : vxvec) rowst[p.first].vals.push_back(p.second), colst[p.second].vals.push_back(p.first);
	for (auto p : vxvec) rowst[p.first].vals.push_back(p.second - 1), colst[p.second].vals.push_back(p.first - 1);
	for (int i = 1; i <= R; ++i) rowst[i].build();
	for (int i = 1; i <= C; ++i) colst[i].build();
	for (auto p : vxvec) {
		if (vxset.find(make_pair(p.first, p.second - 1)) == vxset.end()) rowst[p.first].modify(p.second - 1, 1);
		if (vxset.find(make_pair(p.first - 1, p.second)) == vxset.end()) colst[p.second].modify(p.first - 1, 1);
		if (vxset.find(make_pair(p.first, p.second + 1)) == vxset.end()) rowst[p.first].modify(p.second, 1);
		if (vxset.find(make_pair(p.first + 1, p.second)) == vxset.end()) colst[p.second].modify(p.first, 1);
	}
	// cout << "T " << colst[4].get(3, 3) << endl;
}

int colour(int ar, int ac, int br, int bc) 
{
	int ans = st2d.get(ar, br - 1, ac, bc - 1);
	if (ans == -4) return 1;
	// cout << "S " << ans << endl;
	ans += rowst[ar].get(ac, bc - 1);
	// cout << "S " << ans << endl;
	ans += rowst[br].get(ac, bc - 1);
	// cout << "S " << ans << endl;
	ans += colst[ac].get(ar, br - 1);
	// cout << "S " << ans << endl;
	ans += colst[bc].get(ar, br - 1);
	// cout << "S " << ans << endl;
	ans += ck(ar, ac) + ck(ar, bc) + ck(br, ac) + ck(br, bc);
	// cout << "S " << ans << endl;
	assert(ans % 4 == 0);
	ans /= 4;
	return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Incorrect 2 ms 384 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 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 318 ms 24900 KB Output is correct
4 Correct 461 ms 33940 KB Output is correct
5 Correct 487 ms 33112 KB Output is correct
6 Correct 388 ms 27456 KB Output is correct
7 Correct 446 ms 26904 KB Output is correct
8 Correct 99 ms 12160 KB Output is correct
9 Correct 471 ms 33868 KB Output is correct
10 Correct 498 ms 33112 KB Output is correct
11 Correct 423 ms 27456 KB Output is correct
12 Correct 307 ms 32500 KB Output is correct
13 Correct 326 ms 33944 KB Output is correct
14 Correct 333 ms 33224 KB Output is correct
15 Correct 298 ms 27456 KB Output is correct
16 Correct 375 ms 27348 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 227 ms 43596 KB Output is correct
3 Correct 391 ms 73000 KB Output is correct
4 Correct 570 ms 67440 KB Output is correct
5 Correct 297 ms 58472 KB Output is correct
6 Correct 84 ms 28496 KB Output is correct
7 Incorrect 145 ms 33432 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -