oj.uz

답안 #405034

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405034 2021-05-15T15:32:27 Z BERNARB01 새 집 (APIO18_new_home) C++17
0 / 100
 5000 ms 47748 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5079 ms 47748 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5095 ms 45136 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -