Submission #1043362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043362		vjudge1	New Home (APIO18_new_home)	C++17	0 / 100	1671 ms	186348 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	int n,k,q;
	cin>>n>>k>>q;
	set<int> se;
	map<int,int> com;
	vector<vector<int>> ev,que;
	int t,a,s,e;
	for (int i=0;i<n;i++)
	{
		cin>>a>>t>>s>>e,t--;
		ev.push_back({s,e,a,t});
		se.insert(s),se.insert(e);
	}
	int ans[q]={};
	while (q--)
	{
		int l,y;
		cin>>l>>y;
		se.insert(y);
		que.push_back({y,l,(int)que.size()});
	}
	for (int i:se)
		com[i]=com.size();
	int m=com.size();
	vector<pair<int,int>> st[m],en[m],qu[m];
	for (auto i:ev)
	{
		st[com[i[0]]].push_back({i[2],com[i[3]]});
		en[com[i[1]]].push_back({i[2],com[i[3]]});
	}
	for (auto i:que)
		qu[com[i[0]]].push_back({i[1],com[i[2]]});
	multiset<int> ms[k];
	for (int c=0;c<m;c++)
	{
		for (auto i:st[c])
			ms[i.second].insert(i.first);
		for (auto i:qu[c])
			for (t=0;t<k;t++)
			{
				if (ms[t].empty())
				{
					ans[i.second]=-1;
					break;
				}
				auto x=ms[t].lower_bound(i.first);
				int val=inf;
				if (x!=ms[t].end())
					val=*x-i.first;
				if (x!=ms[t].begin())
				{
					x--;
					val=min(val,i.first-*x);
				}
				ans[i.second]=max(ans[i.second],val);
			}
		for (auto i:en[c])
			ms[i.second].erase(ms[i.second].find(i.first));
	}
	for (int i:ans)
		cout<<i<<' ';
	cout<<endl;
	
	return 0;
}

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