Submission #243040

#	Time	Username	Problem	Language	Result	Execution time	Memory
243040		atoiz	New Home (APIO18_new_home)	C++14	100 / 100	3760 ms	233148 KiB

new_home

/*input
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

1 1 1
100000000 1 1 1
1 1

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 <cstdio>
#include <cassert>
#include <map>
#include <set>

using namespace std;

const int MAXN = 300007, INF = 900 * 1000 * 1000;

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

struct SegmentTree
{
	int N;
	vector<int> A;

	void init(int _N)
	{
		for (N = _N + 5; N & (N - 1); ++N);
		A.assign(N * 2, INF);
	}

	void modify(int l, int r, int x)
	{
		for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
			if (l & 1) minimize(A[l++], x);
			if (r & 1) minimize(A[--r], x);
		}
	}

	int get(int i)
	{
		int ans = INF;
		for (i += N; i >= 1; i >>= 1) minimize(ans, A[i]);
		return ans;
	}
} it;

int N, Q, K;
struct Store { int x, t, a, b, i; } S[MAXN];
struct Border 
{ 
	int x, t, a, b, v; 
	Border(int _x = 0, int _t = 0, int _a = 0, int _b = 0, int _v = 0): x(_x), t(_t), a(_a), b(_b), v(_v) {}
};
struct Query
{
	int x, y, i;
};

int last[MAXN * 2], ans[MAXN];
map<int, vector<int>> events;
set<pair<int, int>> curSet[MAXN];
vector<Border> rightBorder, leftBorder;
vector<Query> queries;
vector<int> times;

void addBorder(pair<int, int> p, pair<int, int> q, int t, int curTime)
{
	int i = p.second, j = q.second;
	int x = (p.first + q.first) >> 1;
	// cout << "add " << i << ' ' << j << ' ' << x << ' ' << curTime << endl;
	int a = last[i], b = curTime;
	last[i] = curTime;
	// if (t == 2) cout << "border " << x << ' ' << a << ' ' << b << ' ' << t << ": " << p.first << ' ' << q.first << " - " << i << endl;
	if (i > N && j > N) {
		leftBorder.emplace_back(-INF, t, a, b, INF);
		rightBorder.emplace_back(INF, t, a, b, -INF);
	} else {
		leftBorder.emplace_back(x, t, a, b, q.first);
		rightBorder.emplace_back(x, t, a, b, p.first);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> K >> Q;
	for (int i = 1; i <= N; ++i) {
		cin >> S[i].x >> S[i].t >> S[i].a >> S[i].b; S[i].i = i;
		// cout << i << ": " << S[i].a << ' ' << S[i].b << endl;
		S[i].x *= 2, ++S[i].b;
		events[S[i].a].push_back(i);
		events[S[i].b].push_back(i);
	}

	for (int t = 1; t <= K; ++t) {
		last[N + t] = 0;
		curSet[t].emplace(-INF, N + t);
		curSet[t].emplace(INF, N + t);
	}

	for (auto ts : events) {
		int curTime = ts.first;
		for (int i : ts.second) {
			int t = S[i].t, x = S[i].x;	
			if (S[i].a == curTime) {
				last[i] = curTime;
				curSet[t].emplace(x, i);
				auto j = curSet[t].find(make_pair(x, i));
				addBorder(*prev(j), *next(j), t, curTime);
			} else {
				auto j = curSet[t].find(make_pair(x, i));
				addBorder(*prev(j), *j, t, curTime);
				addBorder(*j, *next(j), t, curTime);
				curSet[t].erase(j);
			}
		}
	}

	for (int t = 1; t <= K; ++t) addBorder(*curSet[t].begin(), *curSet[t].rbegin(), t, INF);

	times.push_back(-INF);
	for (auto &b : leftBorder) times.push_back(b.a), times.push_back(b.b);
	for (auto &b : rightBorder) times.push_back(b.a), times.push_back(b.b);
	sort(times.begin(), times.end());
	times.erase(unique(times.begin(), times.end()), times.end());
	// for (int x : times) cout << x << ' '; cout << endl;
	for (auto &b : leftBorder) {
		b.a = (int) (upper_bound(times.begin(), times.end(), b.a) - times.begin());
		b.b = (int) (upper_bound(times.begin(), times.end(), b.b) - times.begin());
	}
	for (auto &b : rightBorder) {
		b.a = (int) (upper_bound(times.begin(), times.end(), b.a) - times.begin());
		b.b = (int) (upper_bound(times.begin(), times.end(), b.b) - times.begin());
	}

	queries.resize(Q);
	for (int i = 0; i < Q; ++i) {
		cin >> queries[i].x >> queries[i].y;
		queries[i].x *= 2;
		queries[i].y = (int) (upper_bound(times.begin(), times.end(), queries[i].y) - times.begin());
		queries[i].i = i;
	}
	sort(leftBorder.begin(), leftBorder.end(), [&](Border a, Border b) { return a.x < b.x; });
	sort(rightBorder.begin(), rightBorder.end(), [&](Border a, Border b) { return a.x > b.x; });
	for (int i = 0; i < Q; ++i) ans[i] = -1;

	sort(queries.begin(), queries.end(), [&](Query p, Query q) { return p.x > q.x; });
	it.init((int) times.size());
	auto b = rightBorder.begin();
	for (auto &q : queries) {
		for (; b != rightBorder.end() && b->x >= q.x; ++b) {
			// cout << "r " << b->x << ": " << b->a << ' ' << b->b << ' ' << b->v << endl;
			it.modify(b->a, b->b, b->v);
		}
		int x = it.get(q.y);
		// cout << "g " << q.y << ": " << q.x << " - " << x << ", " << q.i << endl;
		if (x != INF) maximize(ans[q.i], q.x - x);
	}
	// cout << "-" << endl;

	reverse(queries.begin(), queries.end());
	it.init((int) times.size());
	b = leftBorder.begin();
	for (auto &q : queries) {
		for (; b != leftBorder.end() && b->x <= q.x; ++b) {
			// cout << "l " << b->x << ": " << b->a << ' ' << b->b << ' ' << b->v << endl;
			it.modify(b->a, b->b, -b->v);
		}
		int x = -it.get(q.y);
		// cout << "g " << q.y << ": " << q.x << " - " << x << ", " << q.i << endl;
		if (x != -INF) maximize(ans[q.i], x - q.x);
	}
	// cout << "-" << endl;

	for (int i = 0; i < Q; ++i) {
		if (ans[i] >= 200 * 1000 * 1000) ans[i] = -2;
		cout << (ans[i] / 2) << '\n';
	}
}

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