Submission #950862

#	Time	Username	Problem	Language	Result	Execution time	Memory
950862		MinaRagy06	New Home (APIO18_new_home)	C++17	0 / 100	5053 ms	258684 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mid ((l + r) >> 1)

const int N = 300'005;
// set<array<int, 3>> gud[N];
struct segtree {
	set<array<int, 3>> seg[1 << 20];
	void insert(int i, int l, int r, int s, int e, array<int, 3> v) {
		if (s <= l && r <= e) {
			seg[i].insert(v);
			return;
		}
		if (r < s || e < l) {
			return;
		}
		insert(i << 1, l, mid, s, e, v);
		insert(i << 1 | 1, mid + 1, r, s, e, v);
	}
	void erase(int i, int l, int r, int s, int e, array<int, 3> v) {
		if (s <= l && r <= e) {
			seg[i].erase(v);
			return;
		}
		if (r < s || e < l) {
			return;
		}
		if (seg[i].find(v) != seg[i].end()) {
			seg[i].erase(v);
			seg[i << 1].insert(v);
			seg[i << 1 | 1].insert(v);
		}
		erase(i << 1, l, mid, s, e, v);
		erase(i << 1 | 1, mid + 1, r, s, e, v);
	}
	void get(int i, int l, int r, int x, int xv, int &mx, int &cnt) {
		if (seg[i].size()) {
			mx = max(mx, abs(xv - (*seg[i].rbegin())[0]));
			mx = max(mx, abs(xv - (*seg[i].begin())[0]));
			cnt += seg[i].size();
		}
		if (l == r) {
			return;
		}
		if (x <= mid) {
			get(i << 1, l, mid, x, xv, mx, cnt);
		} else {
			get(i << 1 | 1, mid + 1, r, x, xv, mx, cnt);
		}
	}
} seg;
multiset<array<int, 2>> pos[N];
vector<array<int, 2>> ask[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();
		seg.insert(1, 0, v1.size() - 1, v[0], v[1], (array<int, 3>) {val, t, idx});
// 		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();
		seg.erase(1, 0, v1.size() - 1, v[0], v[1], (array<int, 3>) {val, t, idx});
// 		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);
			int mx = 0, cnt = 0;
			seg.get(1, 0, v1.size() - 1, p, x, mx, cnt);
			if (cnt != k) {
				ans[idx] = -1;
				continue;
			}
			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:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for (int i = 0; i < v2.size(); i++) {
      |                  ~~^~~~~~~~~~~

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