Submission #216347

#	Time	Username	Problem	Language	Result	Execution time	Memory
216347		theStaticMind	New Home (APIO18_new_home)	C++14	12 / 100	5075 ms	53740 KiB

new_home

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

struct X{
	int x, t, l, r;
};
struct Query{
	int x, t, id;
};

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, k, q;
	cin >> n >> k >> q;

	vector<X> arr;
	vector<Query> Q;
	vector<int> ans(q, -1);

	for(int i = 0; i < n; i++){
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		arr.pb({a, b, c, d});
	}
	for(int i = 0; i < q; i++){
		int x, y;
		cin >> x >> y;
		Q.pb({x, y, i});
	}

	sort(all(arr), [&](X& a, X& b){return a.l < b.l;});
	sort(all(Q), [&](Query& a, Query& b){return a.t < b.t;});

	vector<int> Y;
	for(int i = 0; i < sz(arr); i++) Y.pb(i);

	sort(all(Y), [&](int x, int y){return arr[x].r < arr[y].r;});

	int a = 0, b = 0;

	multiset<int> data[k + 1];

	for(auto& c : Q){
		while(a < sz(arr) && arr[a].l <= c.t){
			data[arr[a].t].insert(arr[a].x);
			a++;
		}

		while(b < sz(Y) && arr[Y[b]].r < c.t){
			data[arr[Y[b]].t].erase(data[arr[Y[b]].t].find(arr[Y[b]].x));
			b++;
		}

		for(int i = 1; i <= k; i++){
			auto itr = data[i].upper_bound(c.x);
			
			int v = INF;

			if(itr != data[i].end()) v = *itr - c.x;
			if(!data[i].empty() && itr != data[i].begin()){ 
				itr--;
				v = min(v, c.x - *itr);
			}

			if(v == INF){
				ans[c.id] = -1;
				break;
			}
			else{
				ans[c.id] = max(ans[c.id], v);
			}

		}

	}

	for(int i = 0; i < q; i++) cout << ans[i] << "\n";

}

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