Submission #1209152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209152		k1r1t0	New Home (APIO18_new_home)	C++20	57 / 100	5106 ms	794332 KiB

new_home

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;
using qt = array<int, 6>;

const int N = 310000;
const int M = (int)(1e8);

int n, k, q, x[N], t[N], a[N], b[N], ans[N];
multiset<int> st[N];
multiset<array<int, 3>> bw, fw; // pos; val; time
vector<array<int, 3>> ev;
vector<qt> qq;
/*
type = 0; pos; dir (bw = 0, fw = 1); val; time_left; time_right;
type = 1; pos; time; query_id; 0; 0;
*/

void solve(int l, int r, vector<qt> qq) {
	if (qq.empty()) return;
	int last = -M, val = 0;
	for (int i = 0; i < (int) qq.size(); i++) {
		if (qq[i][0] == 0) {
			if (qq[i][4] > l || qq[i][5] < r || qq[i][2] == 0)
				continue;
			val -= qq[i][1] - last;
			last = qq[i][1];
			val = max(val, qq[i][3]);
		} else {
			val -= qq[i][1] - last;
			last = qq[i][1];
			ans[qq[i][3]] = max(ans[qq[i][3]], val);
		}
	}
	last = M + M, val = 0;
	for (int i = qq.size() - 1; i >= 0; i--) {
		if (qq[i][0] == 0) {
			if (qq[i][4] > l || qq[i][5] < r || qq[i][2] == 1)
				continue;
			val -= last - qq[i][1];
			last = qq[i][1];
			val = max(val, qq[i][3]);
		} else {
			val -= last - qq[i][1];
			last = qq[i][1];
			ans[qq[i][3]] = max(ans[qq[i][3]], val);
		}
	}
	if (l == r) return;
	vector<qt> ql, qr;
	int mid = (l + r) / 2;
	for (auto tt : qq) {
		if (tt[0] == 0) {
			if (tt[4] <= l && tt[5] >= r)
				continue;
			if (tt[4] <= mid)
				ql.push_back(tt);
			if (tt[5] >= mid + 1)
				qr.push_back(tt);
		} else {
			if (tt[2] <= mid)
				ql.push_back(tt);
			if (tt[2] >= mid + 1)
				qr.push_back(tt);
		}
	}
	qq.clear();
	qq.shrink_to_fit();
	solve(l, mid, ql);
	solve(mid + 1, r, qr);
}

void fin(int l, int r, int t) {
	int mid = (l + r + M + M) / 2 - M;
	int val1 = mid - l;
	auto it1 = bw.lower_bound({mid, val1, 0});
	int t1 = (*it1)[2];
	bw.erase(it1);
	if (t1 <= t) qq.push_back({0, mid, 0, val1, t1, t});
	int val2 = r - mid - 1;
	auto it2 = fw.lower_bound({mid + 1, val2, 0});
	int t2 = (*it2)[2];
	fw.erase(it2);
	if (t2 <= t) qq.push_back({0, mid + 1, 1, val2, t2, t});
}

void beg(int l, int r, int t) {
	int mid = (l + r + M + M) / 2 - M;
	bw.insert({mid, mid - l, t});
	fw.insert({mid + 1, r - mid - 1, t});
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k >> q;
	for (int i = 1; i <= n; i++) {
		cin >> x[i] >> t[i] >> a[i] >> b[i];
		ev.push_back({a[i], x[i], t[i]});
		ev.push_back({-b[i], x[i], t[i]});
	}
	sort(begin(ev), end(ev), [&] (auto x, auto y) {
		return abs(x[0]) < abs(y[0]) || (abs(x[0]) == abs(y[0]) && x[0] > y[0]);
	});
	for (int i = 1; i <= k; i++) {
		st[i].insert(-M);
		st[i].insert(M + M);
		beg(-M, M + M, 0);
	}
	for (auto [a, x, t] : ev) {
		if (a > 0) {
			int pl = -1, pr = -1;
			auto it = st[t].lower_bound(x);
			pr = *it;
			pl = *prev(it);
			fin(pl, pr, a - 1);
			beg(pl, x, a);
			beg(x, pr, a);
			st[t].insert(x);
		} else {
			int pl = -1, pr = -1;
			auto it = st[t].lower_bound(x);
			pr = *next(it);
			pl = *prev(it);
			fin(pl, x, -a);
			fin(x, pr, -a);	
			beg(pl, pr, -a + 1);
			st[t].extract(x);
		}
	}
	for (int i = 1; i <= k; i++)
		fin(-M, M + M, M);
	for (int i = 1; i <= q; i++) {
		int l, y; cin >> l >> y;
		qq.push_back({1, l, y, i, 0, 0});
		ans[i] = 0;
	}
	sort(begin(qq), end(qq), [&](auto i, auto j) {
		int tpi = (i[0] == 1 ? 1 : (i[2] == 1 ? 0 : 2));
		int tpj = (j[0] == 1 ? 1 : (j[2] == 1 ? 0 : 2));
		return i[1] < j[1] || (i[1] == j[1] && tpi < tpj);
	});
	solve(1, M, qq);
	for (int i = 1; i <= q; i++) {
		if (ans[i] >= M) ans[i] = -1;
		cout << ans[i] << '\n';
	}
}

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