Submission #744404

#	Time	Username	Problem	Language	Result	Execution time	Memory
744404		Abito	New Home (APIO18_new_home)	C++17	0 / 100	5081 ms	157544 KiB

new_home

#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define ep insert
#define pow pwr
#define sqrt sqrtt
#define elif else if
using namespace std;
const int N=1e6+5;
int n,k,q,d[N];
pair<pair<int,int>,pair<int,int>> a[N];
vector<pair<int,int>> adj[2][N];
map<int,int> mp;
multiset<int> s[N];
pair<pair<int,int>,int> b[N];
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>k>>q;
    for (int i=1;i<=n;i++){
        cin>>a[i].F.F>>a[i].F.S>>a[i].S.F>>a[i].S.S;
        mp[a[i].S.F]++;
        mp[a[i].S.S]++;
    }
    int c=1;
    for (int i=1;i<=q;i++){
        cin>>b[i].F.S>>b[i].F.F;
        mp[b[i].F.F]++;
        b[i].S=i;
    }
    for (auto u:mp){
        mp[u.F]=c;
        c++;
    }
    for (int i=1;i<=n;i++){
        a[i].S.F=mp[a[i].S.F];
        a[i].S.S=mp[a[i].S.S];
        adj[0][a[i].S.F].pb(a[i].F);
        adj[1][a[i].S.S].pb(a[i].F);
    }
    for (int i=1;i<=q;i++) b[i].F.F=mp[b[i].F.F];
    sort(b+1,b+1+q);
    int j=1;
    for (int i=1;i<c;i++){
        for (auto u:adj[0][i]) s[u.S].ep(u.F);
        while (b[j].F.F<i) j++;
        while (b[j].F.F==i){
            int ans=INT_MIN;
            for (int l=1;l<=k;l++){
                int ansx=INT_MAX;
                auto it=s[l].lower_bound(b[j].F.S);
                if (it!=s[l].end()) ansx=min(ansx,*it-b[j].F.S);
                if (it!=s[l].begin()) --it;
                if (it!=s[l].end()) ansx=min(ansx,*it-b[j].F.S);
                ans=max(ans,ansx);
            }
            if (ans==INT_MAX) ans=-1;
            d[b[j].S]=ans;
            j++;
        }
        for (auto u:adj[1][i]) s[u.S].erase(s[u.S].find(u.F));
    }
    for (int i=1;i<=q;i++) cout<<d[i]<<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