Submission #54129

#	Time	Username	Problem	Language	Result	Execution time	Memory
54129		Bodo171	New Home (APIO18_new_home)	C++14	12 / 100	3737 ms	59324 KiB

new_home

#include <iostream>
#include <set>
#include <fstream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int nmax=100005;
multiset<int> s[1000];
multiset<int>::iterator it1;
vector<int> v[3*nmax];
map<int,int> m;
int dp[10*nmax],norm[10*nmax],qq[10*nmax];
struct event
{
    int val,wh,mag,tip;
}ev[3*nmax];
int ans[nmax];
int ap[nmax];
int n,k,q,i,j,x,t,a,b,nr,X,mn;
bool compev(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;
    if(n<=60000&&k<=400)
    {
        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,compev);
        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;
    }
    for(i=1;i<=n;i++)
    {
        cin>>x>>t>>a>>b;
        v[t].push_back(x);
        norm[++nr]=x;
    }
    for(i=1;i<=q;i++)
    {
        cin>>qq[i]>>t;
        norm[++nr]=t;
    }
    sort(norm+1,norm+nr+1);
    for(i=1;i<=nr;i++)
        m[norm[i]]=i;
    bool bus=0;
    int st,dr,poz,p,med;
    for(i=1;i<=k;i++)
    {
        if(v[i].empty())
          bus=1;
        else
        {
            sort(v[i].begin(),v[i].end());
            dp[1]=max(dp[1],v[i][0]-norm[1]);
            dp[nr]=max(dp[nr],norm[nr]-v[i].back());
            for(j=0;j<v[i].size()-1;j++)
            {
                st=v[i][j];dr=v[i][j+1];
                med=(v[i][j]+v[i][j+1])/2;poz=0;
                for(p=20;p>=0;p--)
                {
                    if(poz+(1<<p)<=nr&&norm[poz+(1<<p)]<=med) poz+=(1<<p);
                }
                dp[poz]=max(dp[poz],min(dr-norm[poz],norm[poz]-st));
                poz++;
                if(poz>=m[st]&&poz<=m[dr])dp[poz]=max(dp[poz],min(dr-norm[poz],norm[poz]-st));
                poz-=2;
               if(poz>=m[st]&&poz<=m[dr])dp[poz]=max(dp[poz],min(dr-norm[poz],norm[poz]-st));
            }
        }
    }
    for(i=2;i<=nr;i++)
        dp[i]=max(dp[i-1]-(norm[i]-norm[i-1]),dp[i]);
    for(i=nr-1;i>=1;i--)
        dp[i]=max(dp[i+1]-(norm[i+1]-norm[i]),dp[i]);
    for(i=1;i<=q;i++)
    {
        qq[i]=m[qq[i]];
        if(bus) cout<<"-1\n";
        else cout<<dp[qq[i]]<<'\n';
    }
    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:104:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(j=0;j<v[i].size()-1;j++)
                     ~^~~~~~~~~~~~~~

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