Submission #744520

#	Time	Username	Problem	Language	Result	Execution time	Memory
744520		Abito	New Home (APIO18_new_home)	C++17	12 / 100	5102 ms	193128 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
#define y1 YONE
#define int long long
using namespace std;
const int N=1e6+5;
int n,k,q,d[N];
// X , T , L , R
pair<pair<int,int>,pair<int,int>> a[N];
//Y X I
pair<pair<int,int>,int> b[N];
//map for compress
map<int,int> mp;
//v[0] adding , v[1] removing
vector<pair<int,int>> v[2][N];
//for each k what it has
map<int,int> s[N];
int32_t 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]++;
    }
    for (int i=1;i<=q;i++){
        cin>>b[i].F.S>>b[i].F.F;
        b[i].S=i;
        mp[b[i].F.F]++;
    }
    int c=0;
    for (auto u:mp){
        c++;
        mp[u.F]=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];
        v[0][a[i].S.F].pb(a[i].F);
        v[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:v[0][i]) s[u.S][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,abs((*it).F-b[j].F.S));
                if (it!=s[l].begin()) --it;
                if (it!=s[l].end()) ansx=min(ansx,abs((*it).F-b[j].F.S));
                ans=max(ans,ansx);
            }
            if (ans==INT_MAX) ans=-1;
            d[b[j].S]=ans;
            j++;
        }
        for (auto u:v[1][i]){
            s[u.S][u.F]--;
            if (s[u.S][u.F]==0) 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: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20