Submission #698695

#	Time	Username	Problem	Language	Result	Execution time	Memory
698695		vjudge1	New Home (APIO18_new_home)	C++17	5 / 100	5091 ms	20044 KiB

new_home

#include "bits/stdc++.h"
#define ll long long
#define pb push_back
#define endl '\n'
#define sec second
#define fi first

using namespace std;
ll INF= 1e18+79;

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll n,k,q;
    cin>>n>>k>>q;
    //vector<pair<ll,ll>>tms(1e8+1);
    vector<pair<pair<ll,ll>,pair<ll,ll>>>v;
    //map<ll,ll>mp;
    for(int i=0;i<n;i++)
    {
      ll x,t,l,r;
      cin>>x>>t>>l>>r;
      v.pb({{x,t},{l,r}});
      //tms[x]={l,r};
      //mp[x]=t;
    }

    //sort(v.begin(),v.end());
    //--------o(n^2)------
    /*ll nrst[n+1][k+1];

    for(int i=0;i<=n;i++)
      for(int j=0;j<=k;j++)
        nrst[i][j]=INF;

    for(int i=0;i<n;i++)
    {
      for(int j=1;j<=k;j++)
        if(i)
          nrst[i][j]=-(nrst[i-1][j]+(v[i].first-v[i-1].first));
      nrst[i][v[i].second]=0;
    }
    for(int i=n-2;i>=0;i--)
    {
      for(int j=1;j<=k;j++)
          nrst[i][j]=min(abs(nrst[i][j]),( nrst[i+1][j]+(v[i+1].first-v[i].first) ));
    }*/
    //-------------------
    while(q--)
    {
      ll x,y;
      cin>>x>>y;
      ll ans[k+1];
      for(int i=1;i<=k;i++)ans[i]=INF;
      for(int i=0;i<n;i++)
      {
        if(y<=v[i].sec.sec&&y>=v[i].sec.fi)
        {
          ans[v[i].fi.sec]=min(ans[v[i].fi.sec],abs(x-v[i].fi.fi));
        }
      }
      bool m=1;
      ll sol=0;
      for(int i=1;i<=k;i++)
      {
        if(ans[i]==INF)m=0;
        else sol=max(sol,ans[i]);
      }
      if(m)
      cout<<sol<<endl;
      else cout<<-1<<endl;
    }


    return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
*/

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