Submission #54117

#	Time	Username	Problem	Language	Result	Execution time	Memory
54117		Bodo171	New Home (APIO18_new_home)	C++14	12 / 100	3164 ms	10520 KiB

new_home

#include <iostream>
#include <set>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=100005;
multiset<int> s[1000];
multiset<int>::iterator it1;
struct event
{
    int val,wh,mag,tip;
}ev[3*nmax];
int ans[nmax];
int n,k,q,i,j,x,t,a,b,nr,X,mn;
bool comp(event unu,event doi)
{
    if(unu.val==doi.val) return unu.tip<doi.tip;
    return unu.val<doi.val;
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>k>>q;
    for(i=1;i<=n;i++)
    {
        cin>>x>>t>>a>>b;
        ev[++nr]={a,x,t,1};
        ev[++nr]={b+1,x,t,-1};
    }
    for(i=1;i<=q;i++)
    {
        cin>>x>>t;
        ev[++nr]={t,x,i,2};
    }
    sort(ev+1,ev+nr+1,comp);
    for(i=1;i<=nr;i++)
    {
        if(ev[i].tip==1)
        {
            s[ev[i].mag].insert(ev[i].wh);
        }
        if(ev[i].tip==-1)
        {
            s[ev[i].mag].erase(s[ev[i].mag].lower_bound(ev[i].wh));
        }
        if(ev[i].tip==2)
        {
            X=ev[i].wh;
            for(j=1;j<=k&&ans[ev[i].mag]!=-1;j++)
            {
                if(s[j].empty()) ans[ev[i].mag]=-1;
                else
                {
                    mn=1000*1000*100+1;
                    it1=s[j].lower_bound(X);
                    if(it1!=s[j].end()) mn=min(mn,(*it1)-X);
                    if(it1!=s[j].begin()) {it1--;mn=min(mn,X-(*it1));}
                    ans[ev[i].mag]=max(ans[ev[i].mag],mn);
                }
            }
        }
    }
    for(i=1;i<=q;i++)
        cout<<ans[i]<<'\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