oj.uz

답안 #250832

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250832 2020-07-19T09:17:32 Z atoiz 무지개나라 (APIO17_rainbow) C++14
12 / 100
 588 ms 73164 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;
	assert(ans % 4 == 0);
	ans /= 4;
	return ans;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 332 ms 25088 KB Output is correct
4 Correct 507 ms 33832 KB Output is correct
5 Correct 588 ms 33112 KB Output is correct
6 Correct 383 ms 27460 KB Output is correct
7 Correct 451 ms 26908 KB Output is correct
8 Correct 111 ms 12160 KB Output is correct
9 Correct 481 ms 33864 KB Output is correct
10 Correct 514 ms 33240 KB Output is correct
11 Correct 424 ms 27456 KB Output is correct
12 Correct 303 ms 32496 KB Output is correct
13 Correct 311 ms 33868 KB Output is correct
14 Correct 321 ms 33240 KB Output is correct
15 Correct 284 ms 27584 KB Output is correct
16 Correct 348 ms 27264 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 219 ms 43684 KB Output is correct
3 Correct 334 ms 73164 KB Output is correct
4 Correct 522 ms 67404 KB Output is correct
5 Correct 273 ms 58520 KB Output is correct
6 Correct 80 ms 28460 KB Output is correct
7 Incorrect 137 ms 33376 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -