oj.uz

답안 #250802

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250802 2020-07-19T07:57:26 Z atoiz 무지개나라 (APIO17_rainbow) C++14
12 / 100
 1148 ms 136236 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;
	}
	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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 343 ms 18844 KB Output is correct
4 Correct 504 ms 31072 KB Output is correct
5 Correct 515 ms 30472 KB Output is correct
6 Correct 380 ms 23764 KB Output is correct
7 Correct 392 ms 22528 KB Output is correct
8 Correct 86 ms 1640 KB Output is correct
9 Correct 514 ms 31020 KB Output is correct
10 Correct 498 ms 30656 KB Output is correct
11 Correct 406 ms 23828 KB Output is correct
12 Correct 396 ms 29252 KB Output is correct
13 Correct 400 ms 31020 KB Output is correct
14 Correct 392 ms 30656 KB Output is correct
15 Correct 325 ms 23704 KB Output is correct
16 Correct 345 ms 21936 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 277 ms 26076 KB Output is correct
3 Correct 729 ms 136236 KB Output is correct
4 Correct 1148 ms 121132 KB Output is correct
5 Correct 672 ms 94208 KB Output is correct
6 Correct 135 ms 12580 KB Output is correct
7 Runtime error 295 ms 45008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -