Submission #950885

#	Time	Username	Problem	Language	Result	Execution time	Memory
950885		MinaRagy06	New Home (APIO18_new_home)	C++17	47 / 100	5033 ms	307888 KiB

new_home

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

const int N = 300'005;
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;
		}
		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];
array<int, 2> cur[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++) {
		cur[i] = {-1, -2};
		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 update = [&] (int idx, int s, int e) {
// 		cout << idx << " -> " << s << ' ' << e << '\n';
		if (cur[idx][0] <= cur[idx][1]) {
			array<int, 2> v = get(cur[idx][0], cur[idx][1], v1);
			if (v[0] <= v[1]) {
				seg.erase(1, 0, v1.size() - 1, v[0], v[1], (array<int, 3>) {a[idx][0], a[idx][1], idx});
			}
		}
		if (s == -1) {
			cur[idx] = {-1, -2};
			return void();
		}
		cur[idx] = {s, e};
		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>) {a[idx][0], a[idx][1], idx});
	};
// 	auto insert = [&] (int s, int e, int val, int t, int idx) {
// 		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});
// 	};
// 	auto erase = [&] (int s, int e, int val, int t, int idx) {
// 		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 = 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--;
				update(L[1], cur[L[1]][0], md);
				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++;
				update(R[1], md + 1, cur[R[1]][1]);
				r = md;
			}
			it--;
			update(idx, l, r);
		}

		for (auto [x, idx] : ask[i]) {
// 			cout << "? " << x << " (" << idx << ")" << '\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]) {
			update(idx, -1, -1);
			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--;
				update(L[1], cur[L[1]][0], en);
				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++;
				update(R[1], st, cur[R[1]][1]);
				r = md;
			}
			it--;
			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:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |  for (int i = 0; i < v2.size(); i++) {
      |                  ~~^~~~~~~~~~~
new_home.cpp:134:9: warning: variable 'en' set but not used [-Wunused-but-set-variable]
  134 |     int en = 1e8;
      |         ^~
new_home.cpp:146:9: warning: variable 'st' set but not used [-Wunused-but-set-variable]
  146 |     int st = 0;
      |         ^~
new_home.cpp:175:8: warning: variable 'l' set but not used [-Wunused-but-set-variable]
  175 |    int l = 0, r = 1e8;
      |        ^
new_home.cpp:175:15: warning: variable 'r' set but not used [-Wunused-but-set-variable]
  175 |    int l = 0, r = 1e8;
      |               ^

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