Submission #72003

#	Time	Username	Problem	Language	Result	Execution time	Memory
72003		KLPP	New Home (APIO18_new_home)	C++14	12 / 100	5098 ms	95612 KiB

new_home

#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
using namespace std;
typedef long long int lld;
int abs(int x){
	if(x>0)return x;
	return -x;
}
int main(){
	int n,q,k;
	cin>>n>>k>>q;
	int stores[n][4];
	for(int i=0;i<n;i++){
		cin>>stores[i][0]>>stores[i][1]>>stores[i][2]>>stores[i][3];
		stores[i][1]--;
	}
	pair<int,pair<int,int> > queries[q];
	for(int i=0;i<q;i++){int x,y;
		cin>>x>>y;
		queries[i].second.second=i;
		queries[i].second.first=x;
		queries[i].first=y;
	}sort(queries,queries+q);
	
	pair<int,int> v[2*n];
	for(int i=0;i<n;i++){
		v[2*i]=pair<int,int>(stores[i][2],i);
		v[2*i+1]=pair<int,int>(stores[i][3]+1,i);
	}sort(v,v+2*n);
	int pos=0;
	bool used[n];
	for(int i=0;i<n;i++)used[i]=false;
	multiset<int> arr[k];
	int ans[q];
	for(int i=0;i<q;i++){
		while(pos<2*n && v[pos].first<=queries[i].first){
			if(used[v[pos].second]){
				used[v[pos].second]=false;
				int store=v[pos].second;
				std::multiset<int>::iterator it=arr[stores[store][1]].find(stores[store][0]);
				arr[stores[store][1]].erase(it);
			}else{
				used[v[pos].second]=true;
				int store=v[pos].second;
				arr[stores[store][1]].insert(stores[store][0]);
			}
			pos++;
		}
		int xcoord=queries[i].second.first;
		int number=queries[i].second.second;
		for(int j=0;j<k;j++){
			std::multiset<int>::iterator it=arr[j].upper_bound(xcoord);
			int R=1000000000;
			if(it!=arr[j].end()){
				R=min(R,abs(xcoord-*it));
			}
			if(it!=arr[j].begin()){
				it--;
				R=min(R,abs(xcoord-*it));
			}
			ans[number]=max(ans[number],R);
		}
	}
	for(int i=0;i<q;i++){
		if(ans[i]!=1000000000)cout<<ans[i]<<endl;
		else cout<<-1<<endl;
	}
		
	return 0;
}

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