Submission #223339

#	Time	Username	Problem	Language	Result	Execution time	Memory
223339		atoiz	New Home (APIO18_new_home)	C++14	47 / 100	5087 ms	323004 KiB

new_home

/*input
1 1 1
100000000 1 1 1
1 1

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

const int INF = 400 * 1000 * 1000 + 3, MAXN = 300007, MAXC = 100 * 1000 * 1000;

void maximize(int &x, int y) { x = (x > y ? x : y); }

struct SegmentTree {
	int X;
	vector<int> valXs;
	vector<vector<int>> valYs, tree;

	int getPos(vector<int> &vec, int x) { return (int) (lower_bound(vec.begin(), vec.end(), x) - vec.begin()); }

	void init(vector<pair<int, int>> &vec) {
		valXs.clear();
		for (auto p : vec) valXs.push_back(p.first);
		sort(valXs.begin(), valXs.end());
		valXs.erase(unique(valXs.begin(), valXs.end()), valXs.end());

		X = (int) valXs.size();

		valYs.assign(X * 2, vector<int>(0));
		for (auto p : vec) {
			for (int x = getPos(valXs, p.first) + X; x > 0; x >>= 1) {
				valYs[x].push_back(p.second);
			}
		}

		tree.resize(X * 2);
		for (int x = 0; x < 2 * X; ++x) {
			sort(valYs[x].begin(), valYs[x].end());
			valYs[x].erase(unique(valYs[x].begin(), valYs[x].end()), valYs[x].end());
			tree[x].assign(valYs[x].size() * 2, -INF);
		}
	}

	void updSingle(int x, int y1, int y2, int z) {
		for (y1 = getPos(valYs[x], y1) + (int) valYs[x].size(), y2 = getPos(valYs[x], y2) + (int) valYs[x].size(); y1 < y2; y1 >>= 1, y2 >>= 1) {
			if (y1 & 1) maximize(tree[x][y1++], z);
			if (y2 & 1) maximize(tree[x][--y2], z);
		}
	}

	void updMax(int x1, int x2, int y1, int y2, int z) {
		if (y2 < 0 || y1 > MAXC) return;
		// cout << "upd " << x1 << ' ' << x2 << ' ' << y1 << ' ' << y2 << ": " << z << endl;
		for (x1 = getPos(valXs, x1) + X, x2 = getPos(valXs, x2) + X; x1 < x2; x1 >>= 1, x2 >>= 1) {
			if (x1 & 1) updSingle(x1++, y1, y2, z);
			if (x2 & 1) updSingle(--x2, y1, y2, z);
		}
	}

	int getSingle(int x, int y) {
		int ans = -INF;
		for (y = getPos(valYs[x], y) + (int) valYs[x].size(); y > 0; y >>= 1) maximize(ans, tree[x][y]);
		return ans;
	}

	int getMax(int x, int y) {
		int ans = -INF;
		for (x = getPos(valXs, x) + X; x > 0; x >>= 1) maximize(ans, getSingle(x, y));
		return ans;
	}
} lefST, rigST;

struct Event {
	int eventType, storeType, year, pos;
	Event (int _eventType, int _storeType, int _year, int _pos): eventType(_eventType), storeType(_storeType), year(_year), pos(_pos) {}
	bool operator< (const Event &ev) { return year < ev.year; }
};

int N, Q, K;
map<int, pair<int, int>> locations[MAXN];
vector<Event> events;
vector<pair<int, int>> queries;

void apply(int from, int to, int l, int r)
{
	int m = l + ((r - l + 1) >> 1);
	lefST.updMax(from, to, l, m, -l);
	rigST.updMax(from, to, m, r, r);
}

void sweep() {
	for (int t = 1; t <= K; ++t) {
		locations[t][-INF] = locations[t][INF] = make_pair(0, 1);
	}

	for (auto &ev : events) {
		int t = ev.storeType, y = ev.year, p = ev.pos;
		auto &cur = locations[t];
		if (ev.eventType == 0) { // add
			// cout << "add " << y << ": " << t << ' ' << p << endl;
			if (cur.find(p) != cur.end()) {
				++cur[p].second;
				continue;
			}

			auto it = prev(cur.upper_bound(p));
			int l = it -> first, r = next(it) -> first, last = it -> second.first;
			apply(last, y, l, r);

			it -> second.first = y;
			cur[p] = make_pair(y, 1);
		} else {
			// cout << "rem " << y << ": " << t << ' ' << p << endl;
			if ((--cur[p].second)) continue;

			auto it = cur.find(p);
			int l = prev(it) -> first, r = next(it) -> first;
			apply(prev(it) -> second.first, y, l, p);
			apply(it -> second.first, y, p, r);

			prev(it) -> second.first = y;
			cur.erase(it);
		}
	}

	for (int i = 1; i <= K; ++i) {
		for (auto it = locations[i].begin(); it != prev(locations[i].end()); ++it) {
			apply(it -> second.first, INF, it -> first, next(it) -> first);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> K >> Q;

	events.reserve(2 * N);
	for (int i = 0; i < N; ++i) {
		int x, t, a, b;
		cin >> x >> t >> a >> b;
		events.emplace_back(0, t, a, x);
		events.emplace_back(1, t, b + 1, x);
	}
	sort(events.begin(), events.end());

	queries.reserve(Q);
	for (int i = 0; i < Q; ++i) {
		int l, y;
		cin >> l >> y;
		queries.emplace_back(y, l);
	}

	lefST.init(queries);
	rigST.init(queries);

	sweep();

	for (auto &q : queries) {
		int l = -lefST.getMax(q.first, q.second);
		int r = rigST.getMax(q.first, q.second);
		int ans = max(q.second - l, r - q.second);
		if (ans > MAXC) ans = -1;
		cout << ans << '\n';
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 35 / 35
• Subtask 6: 0 / 20