제출 #405034

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

new_home

#include <bits/stdc++.h>

using namespace std;

class bag {
private:
	vector<multiset<long long>> g;
public:
	bag(long long k) {
		g.resize(k);
	}
	void add(long long idx, long long k) {
		g[k].insert(idx);
	}
	void rem(long long idx, long long k) {
		g[k].erase(g[k].find(idx));
	}
	//long long qry(long long lx, long long rx) {
		
	//}
	long long qry(long long x) {
		for (long long k = 0; k < (long long) g.size(); k++) {
			if (g[k].empty()) {
				return -1;
			}
		}
		long long ans = 0;
		for (long long k = 0; k < (long long) 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, abs(x - *lo));
				ans = max(ans, abs(x - *prev(lo)));
			}
		}
		return ans;
	}
};

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

class E {
public:
	long long op, x, ty, ti;
	E(long long opp, long long xx, long long tyy, long long 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);
	long long n, k, q;
	cin >> n >> k >> q;
	vector<E> events;
	for (long long i = 0; i < n; i++) {
		long long 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 (long long i = 0; i < q; i++) {
		long long l, y;
		cin >> l >> y;
		events.emplace_back(E(query, l, i, y));
	}
	sort(events.begin(), events.end());
	vector<long long> ans(q);
	bag mrsrtr(k);
	for (long long i = 0; i < (long long) events.size(); i++) {
		if (events[i].op == start) {
			mrsrtr.add(events[i].x, events[i].ty);
		} else if (events[i].op == query) {
			//long long l = -1, r = 1e8;
			//while (r - l > 1) {
				//long long mid = (l + r) >> 1;
				//if (mrsrtr.qry(max(events[i].x - mid, 0), min(events[i].x + mid, (long long) 1e8)) == k) {
					//r = mid;
				//} else {
					//l = mid;
				//}
				long long r = mrsrtr.qry(events[i].x);
				ans[events[i].ty] = r;
			//}
		} else {
			mrsrtr.rem(events[i].x, events[i].ty);
		}
	}
	for (long long x : ans) {
		cout << x << '\n';
	}
	return 0;
}

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