oj.uz

Submission #250793

# Submission time Handle Problem Language Result Execution time Memory
250793 2020-07-19T07:29:02 Z atoiz Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 1094 ms 136240 KB 
#include "rainbow.h"
#include <iostream>
#include <vector>
#include <algorithm>

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;

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

	// for (auto p : sqvec) cout << p.first << ' ' << p.second << endl;
}

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

	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 Correct 3 ms 384 KB Output is correct
2 Correct 7 ms 768 KB Output is correct
3 Incorrect 3 ms 512 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 312 ms 18844 KB Output is correct
4 Correct 450 ms 31276 KB Output is correct
5 Correct 434 ms 30784 KB Output is correct
6 Correct 340 ms 23960 KB Output is correct
7 Correct 353 ms 22784 KB Output is correct
8 Correct 84 ms 1760 KB Output is correct
9 Correct 486 ms 31272 KB Output is correct
10 Correct 474 ms 30780 KB Output is correct
11 Correct 352 ms 23960 KB Output is correct
12 Correct 348 ms 29632 KB Output is correct
13 Correct 332 ms 31276 KB Output is correct
14 Correct 331 ms 30784 KB Output is correct
15 Correct 308 ms 23956 KB Output is correct
16 Correct 327 ms 22192 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 209 ms 26328 KB Output is correct
3 Correct 642 ms 136240 KB Output is correct
4 Correct 1094 ms 121388 KB Output is correct
5 Correct 676 ms 94080 KB Output is correct
6 Correct 130 ms 12512 KB Output is correct
7 Incorrect 256 ms 21840 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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