제출 #405103

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
405103		BERNARB01	새 집 (APIO18_new_home)	C++17	12 / 100	5085 ms	34216 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

class bag {
private:
	vector<multiset<int>> g;
public:
	bag(int k) {
		g.resize(k);
	}
	void add(int idx, int k) {
		g[k].insert(idx);
	}
	void rem(int idx, int k) {
		g[k].erase(g[k].find(idx));
	}
	//int qry(int lx, int rx) {
		
	//}
	int qry(int x) {
		for (int k = 0; k < (int) g.size(); k++) {
			if (g[k].empty()) {
				return -1;
			}
		}
		int ans = 0;
		for (int k = 0; k < (int) g.size(); k++) {
			auto lo = g[k].lower_bound(x);
			if (lo == g[k].end()) {
				ans = max(ans, abs(x - *prev(lo)));
			} else if (lo == g[k].begin()) {
				ans = max(ans, abs(x - *lo));
			} else {
				ans = max(ans, min(abs(x - *lo), abs(x - *prev(lo))));
			}
		}
		return ans;
	}
};

const int start = 0;
const int query = 1;
const int endd = 2;

class E {
public:
	int op, x, ty, ti;
	E(int opp, int xx, int tyy, int tii) {
		op = opp;
		x = xx;
		ty = tyy;
		ti = tii;
	}
	bool operator <(const E& o) {
		if (ti == o.ti) {
			return op < o.op;
		}
		return ti < o.ti;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k, q;
	cin >> n >> k >> q;
	vector<E> events;
	for (int i = 0; i < n; i++) {
		int x, t, a, b;
		cin >> x >> t >> a >> b;
		--t;
		events.emplace_back(E(start, x, t, a));
		events.emplace_back(E(endd, x, t, b));
	}
	for (int i = 0; i < q; i++) {
		int l, y;
		cin >> l >> y;
		events.emplace_back(E(query, l, i, y));
	}
	sort(events.begin(), events.end());
	vector<int> ans(q);
	bag mrsrtr(k);
	for (int i = 0; i < (int) events.size(); i++) {
		if (events[i].op == start) {
			mrsrtr.add(events[i].x, events[i].ty);
		} else if (events[i].op == query) {
			//int l = -1, r = 1e8;
			//while (r - l > 1) {
				//int mid = (l + r) >> 1;
				//if (mrsrtr.qry(max(events[i].x - mid, 0), min(events[i].x + mid, (int) 1e8)) == k) {
					//r = mid;
				//} else {
					//l = mid;
				//}
				int r = mrsrtr.qry(events[i].x);
				ans[events[i].ty] = r;
			//}
		} else {
			mrsrtr.rem(events[i].x, events[i].ty);
		}
	}
	for (int x : ans) {
		cout << x << '\n';
	}
	return 0;
}

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