oj.uz

Submission #405030

# Submission time Handle Problem Language Result Execution time Memory
405030 2021-05-15T15:26:45 Z BERNARB01 New Home (APIO18_new_home) C++17
0 / 100
 5000 ms 46116 KB 
#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, abs(x - *lo));
				ans = max(ans, 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
0 / 5.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Execution timed out 5062 ms 46116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5003 ms 43068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -