Submission #726539

#	Time	Username	Problem	Language	Result	Execution time	Memory
726539		hollwo_pelw	New Home (APIO18_new_home)	C++17	0 / 100	5077 ms	520992 KiB

new_home

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen(".inp", "r"))
		assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
	using namespace chrono;
	auto start = steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = steady_clock::now();
	cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

const int N = 3e5 + 5, M = 9e5 + 5;

vector<int> xval, yval;

int n, k, q, px[N], py[N], res[N], cnt_type;
vector<pair<int, int>> stores[N];

map<int, int> st[N];
vector<pair<int, int>> upd[M], que[M];

#define tm ((tl + tr) >> 1)
#define left id << 1, tl, tm
#define right id << 1 | 1, tm + 1, tr

struct segtree {
	multiset<int> st[N << 3];
	void update(int l, int r, int v, int s, int id = 1, int tl = 1, int tr = xval.size()) {
		// if (id == 1) cout << "MAX " << l << ' ' << r << " : " << (s < 0 ? "DEL " : "ADD ") << v << '\n';
		if (l > tr || tl > r) return ;
		if (l <= tl && tr <= r) {
			// cout << id << " -> " << v << '\n';
			if (s < 0)
				st[id].erase(st[id].find(v));
			else
				st[id].insert(v);
			return ;
		}
		update(l, r, v, s, left), update(l, r, v, s, right);
	}
	int query(int p, int id = 1, int tl = 1, int tr = xval.size()) {
		int res = st[id].empty() ? 0 : max(xval[p] - *st[id].begin(), *--st[id].end() - xval[p]);
		// cout << "get " << p << '\n';
		// cout << " --> " << res << '\n';
		// cout << st[id].size() << '\n';
		if (tl < tr)
			res = max(res, (p > tm ? query(p, right) : query(p, left)));
		return res;
	}
} T;

inline void addseg(int l, int r, int v) {
	// cout << "add seg " << l << ' ' << r << ' ' << v << '\n';
	if (l < 1 && r > n) { // empty ?
		// cout << "sus \n";
		cnt_type -= v;
		return ;
	}
	if (l < 1) {
		T.update(1, r - 1, xval[r], v);
		return ;
	}
	if (r > n) {
		T.update(l + 1, n, xval[l], v);
		return ;
	}

	int ml = (l + r) >> 1, mr = ml + 1;
	T.update(l + 1, ml, xval[l], v);
	T.update(mr, r - 1, xval[r], v);
}

void add(int x, map<int, int> &st) {
	if ((++ st[x]) == 1) {
		auto it = st.find(x);
		int l = prev(it) -> first, r = next(it) -> first;
		// cout << x << '\n';
		// cout << l << ' ' << r << '\n';

		addseg(l, r, -1);
		addseg(l, x, +1);
		addseg(x, r, +1);
	}
}

void del(int x, map<int, int> &st) {
	if ((-- st[x]) == 0) {
		auto it = st.find(x);
		int l = prev(it) -> first, r = next(it) -> first;

		addseg(l, r, +1);
		addseg(l, x, -1);
		addseg(x, r, -1);
		st.erase(x);
	}
}

void Hollwo_Pelw(){
	cin >> n >> k >> q;
	for (int i = 1, x, a, b, t; i <= n; i++) {
		cin >> x >> t >> a >> b, ++ b;
		xval.push_back(x);
		yval.push_back(a);
		yval.push_back(b);
		stores[t].emplace_back(a, +x);
		stores[t].emplace_back(b, -x);
	}

	for (int i = 1; i <= q; i++) {
		cin >> px[i] >> py[i];
		xval.push_back(px[i]);
		yval.push_back(py[i]);
	}

	xval.push_back(0);
	yval.push_back(0);

	sort(xval.begin(), xval.end());
	sort(yval.begin(), yval.end());

	xval.erase(unique(xval.begin(), xval.end()), xval.end());
	yval.erase(unique(yval.begin(), yval.end()), yval.end());

	for (int i = 1; i <= q; i++) {
		px[i] = lower_bound(xval.begin(), xval.end(), px[i]) - xval.begin();
		py[i] = lower_bound(yval.begin(), yval.end(), py[i]) - yval.begin();
		que[py[i]].emplace_back(px[i], i);
	}

	n = xval.size();

	for (int t = 1; t <= k; t++) { 
		st[t][0] = st[t][n + 1] = 1;
		for (auto &[y, x] : stores[t]) {
			y = lower_bound(yval.begin(), yval.end(), y) - yval.begin();
			x = (x < 0 ? -1 : +1) * (lower_bound(xval.begin(), xval.end(), abs(x)) - xval.begin());
			upd[y].emplace_back(t, x);
		}
	}


	for (int y = 1; y < (int) yval.size(); y++) {
		// cout << "TIME LINE y = " << yval[y] << '\n';
		// cout << "---------------------------------\n";
		for (auto [t, x] : upd[y]) {
			if (x < 0) {
				// cout << "DEL " << -x << ' ' << t << '\n';
				del(-x, st[t]);
			}
			else {
				// cout << "ADD " << +x << ' ' << t << '\n';
				add(+x, st[t]);
			}
		}
		// cout << "cnt = " << cnt_type << '\n';
		for (auto [p, i] : que[y]) {
			// cout << "QUERY " << p << ' ' << i << '\n'; 
			if (cnt_type == k) {
				res[i] = T.query(p);
			}
			else {
				res[i] = -1;
			}
		}
		// cout << "---------------------------------\n";
	}

	for (int i = 1; i <= q; i++) {
		cout << res[i] << '\n';
	}
}

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