Submission #950861

#	Time	Username	Problem	Language	Result	Execution time	Memory
950861		MinaRagy06	New Home (APIO18_new_home)	C++17	5 / 100	2220 ms	1048576 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 300'005;
multiset<array<int, 2>> pos[N];
vector<array<int, 2>> ask[N];
set<array<int, 3>> gud[N];
vector<array<int, 3>> in[N], out[N];
int ans[N];
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, k, q;
	cin >> n >> k >> q;
	array<int, 4> a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
	}
	array<int, 2> qq[q];
	vector<int> v1, v2;
	for (int i = 0; i < q; i++) {
		cin >> qq[i][0] >> qq[i][1];
		v1.push_back(qq[i][0]);
		v2.push_back(qq[i][1]);
	}
	
	sort(v1.begin(), v1.end());
	v1.resize(unique(v1.begin(), v1.end()) - v1.begin());

	sort(v2.begin(), v2.end());
	v2.resize(unique(v2.begin(), v2.end()) - v2.begin());

	auto get = [&] (int s, int e, vector<int> &vv) {
		int l = lower_bound(vv.begin(), vv.end(), s) - vv.begin();
		int r = upper_bound(vv.begin(), vv.end(), e) - vv.begin() - 1;
		return (array<int, 2>) {l, r};
	};
	auto get2 = [&] (int x, vector<int> &vv) {
		return lower_bound(vv.begin(), vv.end(), x) - vv.begin();
	};
	
	for (int i = 0; i < n; i++) {
		array<int, 2> v = get(a[i][2], a[i][3], v2);
		if (v[0] > v[1]) continue;
		in[v[0]].push_back({a[i][0], a[i][1], i});
		out[v[1]].push_back({a[i][0], a[i][1], i});
	}
	for (int i = 0; i < q; i++) {
		ask[get2(qq[i][1], v2)].push_back({qq[i][0], i});
	}
	auto insert = [&] (int s, int e, int val, int t, int idx) {
// 		cout << "+ " << s << ' ' << e << ' ' << val << '\n';
		array<int, 2> v = get(s, e, v1);
		if (v[0] > v[1]) return void();
		for (int i = v[0]; i <= v[1]; i++) {
			gud[i].insert({val, t, idx});
		}
	};
	auto erase = [&] (int s, int e, int val, int t, int idx) {
// 		cout << "- " << s << ' ' << e << ' ' << val << '\n';
		array<int, 2> v = get(s, e, v1);
		if (v[0] > v[1]) return void();
		for (int i = v[0]; i <= v[1]; i++) {
			gud[i].erase({val, t, idx});
		}
	};
	for (int i = 0; i < v2.size(); i++) {
		for (auto [x, t, idx] : in[i]) {
			pos[t].insert({x, idx});
			auto it = pos[t].lower_bound({x, idx});
			int l = 0, r = 1e8;
			if (it != pos[t].begin()) {
				it--;
				array<int, 2> L = (*it);
				int md = (L[0] + x) / 2;
				it++;
				it++;
				int en = 1e8;
				if (it != pos[t].end()) {
					en = (L[0] + (*it)[0]) / 2;
				}
				it--;
				erase(md + 1, en, L[0], t, L[1]);
				l = md + 1;
			}
			if ((++it) != pos[t].end()) {
				array<int, 2> R = (*it);
				int md = (x + R[0]) / 2;
				it--;
				int st = 0;
				if (it != pos[t].begin()) {
					it--;
					st = ((*it)[0] + R[0]) / 2 + 1;
					it++;
				}
				it++;
				erase(st, md, R[0], t, R[1]);
				r = md;
			}
			it--;
			insert(l, r, x, t, idx);
		}

		for (auto [x, idx] : ask[i]) {
// 			cout << "? " << v2[i] << '\n';
			int p = get2(x, v1);
			if (gud[p].size() != k) {
				ans[idx] = -1;
				continue;
			}
			int mx = 0;
			for (auto [j, t, idx2] : gud[p]) {
				mx = max(mx, abs(j - x));
			}
			ans[idx] = mx;
		}
		
		for (auto [x, t, idx] : out[i]) {
			auto it = pos[t].lower_bound({x, idx});
			int l = 0, r = 1e8;
			if (it != pos[t].begin()) {
				it--;
				array<int, 2> L = (*it);
				int md = (L[0] + x) / 2;
				it++;
				it++;
				int en = 1e8;
				if (it != pos[t].end()) {
					en = (L[0] + (*it)[0]) / 2;
				}
				it--;
				insert(md + 1, en, L[0], t, L[1]);
				l = md + 1;
			}
			if ((++it) != pos[t].end()) {
				array<int, 2> R = (*it);
				int md = (x + R[0]) / 2;
				it--;
				int st = 0;
				if (it != pos[t].begin()) {
					it--;
					st = ((*it)[0] + R[0]) / 2 + 1;
					it++;
				}
				it++;
				insert(st, md, R[0], t, R[1]);
				r = md;
			}
			it--;
			erase(l, r, x, t, idx);
			pos[t].erase({x, idx});
		}
	}
	for (int i = 0; i < q; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (int i = 0; i < v2.size(); i++) {
      |                  ~~^~~~~~~~~~~
new_home.cpp:107:22: warning: comparison of integer expressions of different signedness: 'std::set<std::array<int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |    if (gud[p].size() != k) {
      |        ~~~~~~~~~~~~~~^~~~

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