oj.uz

Submission #250827

# Submission time Handle Problem Language Result Execution time Memory
250827 2020-07-19T09:15:19 Z atoiz Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 554 ms 73036 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);
	// 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;
	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 315 ms 24960 KB Output is correct
4 Correct 517 ms 33940 KB Output is correct
5 Correct 478 ms 33112 KB Output is correct
6 Correct 389 ms 27456 KB Output is correct
7 Correct 439 ms 26908 KB Output is correct
8 Correct 90 ms 12160 KB Output is correct
9 Correct 477 ms 33864 KB Output is correct
10 Correct 490 ms 33112 KB Output is correct
11 Correct 393 ms 27660 KB Output is correct
12 Correct 296 ms 32500 KB Output is correct
13 Correct 300 ms 33872 KB Output is correct
14 Correct 332 ms 33176 KB Output is correct
15 Correct 278 ms 27456 KB Output is correct
16 Correct 353 ms 27392 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 223 ms 43596 KB Output is correct
3 Correct 333 ms 73036 KB Output is correct
4 Correct 554 ms 67532 KB Output is correct
5 Correct 286 ms 58396 KB Output is correct
6 Correct 77 ms 28460 KB Output is correct
7 Incorrect 140 ms 33504 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 -