Submission #545419

#	Time	Username	Problem	Language	Result	Execution time	Memory
545419		valerikk	New Home (APIO18_new_home)	C++17	0 / 100	5064 ms	149256 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e8;
const int N = 3e5 + 7;

struct Store {
	int x, t, a, b;
};

struct Query {
	int l, y;
};

int n, k, q;
Store st[N];
Query qq[N];
vector<int> ys;
vector<int> beg[N], en[N];
int m;
int ans[N];
set<pair<int, int>> s[N];
int mn[2 * N];

void upd(int l, int r, int x) {
	l += m, r += m;
	while (l < r) {
		if (l & 1) {
			mn[l] = min(mn[l], x);
			++l;
		}
		if (r & 1) {
			--r;
			mn[r] = min(mn[r], x);
		}
		l >>= 1, r >>= 1;
	}
}

int get(int i) {
	i += m;
	int res = INF + 1;
	for (; i > 0; i >>= 1) {
		res = min(res, mn[i]);
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k >> q;
	for (int i = 0; i < n; ++i) {
		auto &[x, t, a, b] = st[i];
		cin >> x >> t >> a >> b;
	}
	for (int i = 0; i < q; ++i) {
		auto &[l, y] = qq[i];
		cin >> l >> y;
		ys.push_back(y);
	}

	sort(ys.begin(), ys.end());
	ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
	m = ys.size();

	for (int i = 0; i < n; ++i) {
		st[i].a = lower_bound(ys.begin(), ys.end(), st[i].a) - ys.begin();
		st[i].b = lower_bound(ys.begin(), ys.end(), st[i].b + 1) - ys.begin();
		--st[i].t;
	}
	for (int i = 0; i < q; ++i) {
		qq[i].y = lower_bound(ys.begin(), ys.end(), qq[i].y) - ys.begin();
	}

	for (int i = 0; i < n; ++i) {
		beg[st[i].a].push_back(i);
		en[st[i].b].push_back(i);
	}

	for (int _ = 0; _ < 2; ++_) {
		for (int i = 0; i < k; ++i) {
			s[i].clear();
			s[i].insert({0, -1});
			s[i].insert({INF + 1, -1});
		}

		map<pair<int, int>, vector<pair<int, int>>> mp;
		
		auto kek = [&](int x1, int x2, int y, int type) {
			if (x1 == 0) return;
			if (x1 < x2) {
				if (x2 != INF + 1) {
					x2 = (x1 + x2 + 1) / 2;
				}
				mp[{x1, x2}].push_back({y, type});
			}
		};

		for (int i = 0; i <= m; ++i) {
			for (int id : beg[i]) {
				auto [it, fl] = s[st[id].t].insert({st[id].x, id});
				assert(fl);
				kek(prev(it)->first, st[id].x, i, 1);
				kek(st[id].x, next(it)->first, i, 1);
				kek(prev(it)->first, next(it)->first, i, -1);
			}
			for (int id : en[i]) {
				auto it = s[st[id].t].find({st[id].x, id});
				kek(prev(it)->first, st[id].x, i, -1);
				kek(st[id].x, next(it)->first, i, -1);
				kek(prev(it)->first, next(it)->first, i, 1);
				s[st[id].t].erase(it);
			}
		}

		vector<pair<int, int>> ord;
		for (const auto &[p, v] : mp) {
			ord.push_back(p);
		}
		sort(ord.begin(), ord.end(), [&](const auto &p1, const auto &p2) {
			return p1.second > p2.second;
		});

		vector<int> qord(q);
		iota(qord.begin(), qord.end(), 0);
		sort(qord.begin(), qord.end(), [&](const int &i, const int &j) {
			return qq[i].l > qq[j].l;
		});

		for (int i = 0; i < 2 * m; ++i) {
			mn[i] = INF;
		}

		int ptr = 0;
		for (int i = 0; i < q; ++i) {
			while (ptr < (int)ord.size() && ord[ptr].second > qq[qord[i]].l) {
				const auto &v = mp[ord[ptr]];
				int bal = 0;
				for (int j = 0; j + 1 < (int)v.size(); ++j) {
					bal += v[j].second;
					if (bal > 0) {
						upd(v[j].first, v[j + 1].first, ord[ptr].first);
					}
				}
				++ptr;
			}
			ans[qord[i]] = max(ans[qord[i]], qq[qord[i]].l - get(qq[qord[i]].y));
		}


		for (int i = 0; i < n; ++i) {
			st[i].x = INF - st[i].x + 1;
		}
		for (int i = 0; i < q; ++i) {
			qq[i].l = INF - qq[i].l + 1;
		}
	}

	vector<int> cnt(k, 0);
	vector<bool> good(m + 1);
	int z = k;
	for (int i = 0; i <= m; ++i) {
		for (int id : beg[i]) {
			z -= cnt[st[id].t] == 0;
			++cnt[st[id].t];
			z += cnt[st[id].t] == 0;
		}
		for (int id : en[i]) {
			z -= cnt[st[id].t] == 0;
			--cnt[st[id].t];
			z += cnt[st[id].t] == 0;
		}
		good[i] = z == 0;
	}
	for (int i = 0; i < q; ++i) {
		if (!good[qq[i].y]) {
			cout << "-1\n";
		} else {
			cout << ans[i] << "\n";
		}
	}


	return 0;
}

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