Submission #264560

#	Time	Username	Problem	Language	Result	Execution time	Memory
264560		dsjong	New Home (APIO18_new_home)	C++14	12 / 100	2857 ms	11376 KiB

new_home

#include <bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
using namespace std;
int ans[300005];
int x[300005], t[300005], a[300005], b[300005];
set<pii>sa[405], sb[405];
multiset<int>sx[405];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, k, q;
	cin>>n>>k>>q;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>t[i]>>a[i]>>b[i];
		sa[t[i]].insert({a[i], i});
	}
	vector<pair<pii, int>>queries;
	for(int i=1;i<=q;i++){
		int l, y;
		cin>>l>>y;
		queries.push_back({{y, l}, i});
	}
	sort(queries.begin(), queries.end());
	for(auto p:queries){
		int y=p.F.F, l=p.F.S, idx=p.S;
		int fans=0;
		for(int i=1;i<=k;i++){
			while(!sa[i].empty()){
				auto it=sa[i].begin();
				if(it->F <= y){
					sb[i].insert({b[it->S], it->S});
					sx[i].insert(x[it->S]);
				}
				else break;
				sa[i].erase(it);
			}

			while(!sb[i].empty()){
				auto it=sb[i].begin();
				if(it->F < y){
					sx[i].erase(sx[i].find(x[it->S]));
					sb[i].erase({b[it->S], it->S});
				}
				else break;
			}
			int cur=1e9;
			auto it=sx[i].lower_bound(l);
			if(it!=sx[i].end()) cur=min(cur, abs(*it - l));
			if(!sx[i].empty() && it!=sx[i].begin()){
				it--;
				cur=min(cur, abs(*it - l));
			}
			fans=max(fans, cur);
		}
		if(fans==1e9) fans=-1;
		ans[idx]=fans;
	}
	for(int i=1;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