Submission #734541

#	Time	Username	Problem	Language	Result	Execution time	Memory
734541		hollwo_pelw	New Home (APIO18_new_home)	C++17	100 / 100	2032 ms	99208 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, maxC = 1e8;

int n, k, q, x[N], y[2 * N], st[N * 8], res[N];
vector<int> valy = {0};
vector<pair<int, int>> stores[N];

struct query_t {
	int x, y, id;
	bool operator < (const query_t &oth) const {
		return tuple<int, int, int>(x, y, id) < tuple<int, int, int>(oth.x, oth.y, oth.id); 
	}
} queries[N];
struct update_t {
	int x, v, ly, ry;
	bool operator < (const update_t &oth) const {
		return tuple<int, int, int, int>(x, v, ly, ry) < tuple<int, int, int, int>(oth.x, oth.v, oth.ly, oth.ry);
	}
};

struct cmp {
	bool operator () (const int &i, const int &j) const {
		return x[i] < x[j] || (x[i] == x[j] && i < j);
	}
};

inline void update(int l, int r, int v) {
	for (l += valy.size(), r += valy.size(); l < r; l >>= 1, r >>= 1) {
		if (l & 1) st[l] = max(st[l], v), l ++;
		if (r & 1) r --, st[r] = max(st[r], v);
	}
}

inline int query(int p) {
	int res = 0;
	for (p += valy.size(); p; p >>= 1) {
		res = max(res, st[p]);
	}
	return res;
}

void solve() {
	// cout << "SOLVE" << endl;

	map<int, int, cmp> mp;
	vector<update_t> upds;

	for (int i = 1; i <= k; i++) {
		// cout << "STORE " << i << '\n';
		mp[0] = mp[n + 1] = 0;

		for (auto [y, id] : stores[i]) {
			if (mp.count(id)) {
				// cout << "REM " << id << " at time " << y << '\n';
				auto p = mp.find(id), r = next(p), l = prev(p);
				upds.push_back({(x[p -> first] + x[r -> first] + 1) / 2, x[r -> first], r -> second, y});
				// cout << "-> " << upds.back().x << ' ' << upds.back().v << ' ' << upds.back().ly << ' ' << upds.back().ry << '\n';
				upds.push_back({(x[l -> first] + x[p -> first] + 1) / 2, x[p -> first], p -> second, y});
				// cout << "-> " << upds.back().x << ' ' << upds.back().v << ' ' << upds.back().ly << ' ' << upds.back().ry << '\n';
				r -> second = y;
				mp.erase(p);
			} else {
				// cout << "ADD " << id << " at time " << y << '\n';
				mp[id] = y;
				auto p = mp.find(id), r = next(p), l = prev(p);
				upds.push_back({(x[l -> first] + x[r -> first] + 1) / 2, x[r -> first], r -> second, y});
				// cout << "-> " << upds.back().x << ' ' << upds.back().v << ' ' << upds.back().ly << ' ' << upds.back().ry << '\n';
				r -> second = y;
			}
		}

		upds.push_back({0, 2 * maxC, mp[n + 1], (int) valy.size()});
	}
	sort(upds.begin(), upds.end());

	// cout << "--------------\n";

	memset(st, 0, sizeof st);
	for (int i = 1, j = 0; i <= q; i++) {
		// cout << "POS = " << queries[i].x << '\n';
		for (; j < (int) upds.size() && upds[j].x <= queries[i].x; j ++) {
			auto p = upds[j]; update(p.ly, p.ry, p.v);
			// cout << "UPD " << p.ly << ' ' << p.ry << ' ' << p.v << '\n';
		}
		// cout << "ASK time = " << queries[i].y << '\n';
		res[queries[i].id] = max(res[queries[i].id], query(queries[i].y) - queries[i].x);
	}
}

void Hollwo_Pelw(){
	cin >> n >> k >> q;
	for (int i = 1, tp, ly, ry; i <= n; i++) {
		cin >> x[i] >> tp >> ly >> ry, ++ ry;
		stores[tp].push_back({ly, i});
		stores[tp].push_back({ry, i});
		valy.push_back(ly);
		valy.push_back(ry);
	}
	x[0] = - 2 * maxC, x[n + 1] = 2 * maxC;

	sort(valy.begin(), valy.end());
	for (int i = 1; i <= k; i++) {
		for (auto &[y, id] : stores[i])
			y = upper_bound(valy.begin(), valy.end(), y) - valy.begin() - 1; 
		sort(stores[i].begin(), stores[i].end());
	}
	for (int i = 1; i <= q; i++) {
		cin >> queries[i].x >> queries[i].y;
		queries[i].id = i;
		queries[i].y = upper_bound(valy.begin(), valy.end(), queries[i].y) - valy.begin() - 1;
	}

	sort(queries + 1, queries + q + 1);

	for (int iter = 2; iter --; ) {

		solve();

		for (int i = 1; i <= n; i++)
			x[i] = maxC - x[i];
		for (int i = 1; i <= q; i++)
			queries[i].x = maxC - queries[i].x;
		reverse(queries + 1, queries + q + 1);
	}

	for (int i = 1; i <= q; i++) {
		cout << (res[i] >= maxC ? -1 : res[i]) << '\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