Submission #51184

#	Time	Username	Problem	Language	Result	Execution time	Memory
51184		zetapi	New Home (APIO18_new_home)	C++14	12 / 100	3350 ms	77616 KiB

new_home

#include <bits/stdc++.h>
using namespace std;

#define pb  push_back
#define mp  make_pair
#define int long long
#define itr ::iterator 

typedef pair<int,int>  pii;

const int MAX=1e5;
const int INF=1e12;

multiset<int> st[500];
multiset<int> itr it;

vector< pair<int,pii> > vec;

struct node
{
	int pos,type,start,end;
}	arr[MAX];

int N,K,Q,ind,lol,loc[MAX],year[MAX],res[MAX];

signed main()
{
	ios_base::sync_with_stdio(false);
	/*cin.tie(0);
	cout.tie(0);*/

	cin>>N>>K>>Q;
	for(int A=1;A<=N;A++)
	{
		cin>>arr[A].pos>>arr[A].type>>arr[A].start>>arr[A].end;
		vec.pb(mp(arr[A].start,mp(0,A)));
		vec.pb(mp(arr[A].end,mp(2,A)));
	}
	for(int A=1;A<=Q;A++)
	{
		cin>>loc[A]>>year[A];
		vec.pb(mp(year[A],mp(1,A)));
	}
	sort(vec.begin(),vec.end());
	for(auto A:vec)
	{
		ind=A.second.second;
		if(A.second.first==0)
			st[arr[ind].type].insert(arr[ind].pos);
		else if(A.second.first==1)
		{
			for(int B=1;B<=K;B++)
			{
				if(st[B].empty())
				{
					res[ind]=-1;
					break;
				}
				else
				{
					lol=INF;
					it=st[B].lower_bound(loc[ind]);
					if(it!=st[B].end())
						lol=min(lol,abs(loc[ind]-*it));
					if((it--)!=st[B].begin())
						lol=min(lol,abs(loc[ind]-*it));
					res[ind]=max(res[ind],lol);
				}
			}
		}
		else
			st[arr[ind].type].erase(st[arr[ind].type].find(arr[ind].pos));
	}
	for(int A=1;A<=Q;A++)
		cout<<res[A]<<"\n";
	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