Submission #521781

#	Time	Username	Problem	Language	Result	Execution time	Memory
521781		CSQ31	New Home (APIO18_new_home)	C++17	12 / 100	5102 ms	42656 KiB

new_home

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5+5;
int x[MAXN],t[MAXN];
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,q,k;
	cin>>n>>k>>q;
	vector<multiset<int>>store(k+1);
	vector<array<int,2>>s;
	for(int i=1;i<=n;i++){
		int a,b;
		cin>>x[i]>>t[i]>>a>>b;
		s.push_back({a,-i});
		s.push_back({b+1,i});
	}
	sort(s.begin(),s.end());
	vector<int>l(q),y(q),id(q);
	vector<int>ans(q,0);
	for(int i=0;i<q;i++){
		cin>>l[i]>>y[i];
		id[i] = i;
	}
	sort(id.begin(),id.end(),[&](const int &i,const int &j){return y[j] > y[i];});
	int ptr = -1;
	for(int i=0;i<q;i++){
		while(ptr+1<2*n && s[ptr+1][0] <= y[id[i]]){
			ptr++;
			int j = s[ptr][1];
			//cout<<i<<" "<<j<<'\n';
			if(j < 0)store[t[-j]].insert(x[-j]);
			else store[t[j]].erase(store[t[j]].find(x[j]));
		}
		for(int j=1;j<=k;j++){
			int c = 1e9;
			auto it = store[j].lower_bound(l[id[i]]);
			if(it != store[j].end())c = min(c,*it-l[id[i]]);
			if(it != store[j].begin()){
				it--;
				c = min(c,l[id[i]] - *it);
			}
			ans[id[i]] = max(ans[id[i]],c);
		}
		if(ans[id[i]] == 1e9)ans[id[i]] = -1;
		
	}
	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