oj.uz

Submission #744397

# Submission time Handle Problem Language Result Execution time Memory
744397 2023-05-18T14:12:28 Z Abito New Home (APIO18_new_home) C++17
0 / 100
 5000 ms 170460 KB 
#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;
set<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,abs(*it-b[j].F.S));
                    ++it;
                }elif (it!=s[l].begin()) --it;
                if (it!=s[l].end()){
                    ansx=min(ansx,abs(*it-b[j].F.S));
                    ++it;
                }elif (it!=s[l].begin()) --it;
                //cout<<l<<' '<<ansx<<endl;
                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(u.F);
    }
    for (int i=1;i<=q;i++) cout<<d[i]<<endl;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94156 KB Output is correct
2 Correct 48 ms 94292 KB Output is correct
3 Correct 46 ms 94164 KB Output is correct
4 Incorrect 49 ms 94228 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94156 KB Output is correct
2 Correct 48 ms 94292 KB Output is correct
3 Correct 46 ms 94164 KB Output is correct
4 Incorrect 49 ms 94228 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5066 ms 149980 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5080 ms 170460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94156 KB Output is correct
2 Correct 48 ms 94292 KB Output is correct
3 Correct 46 ms 94164 KB Output is correct
4 Incorrect 49 ms 94228 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94156 KB Output is correct
2 Correct 48 ms 94292 KB Output is correct
3 Correct 46 ms 94164 KB Output is correct
4 Incorrect 49 ms 94228 KB Output isn't correct
5 Halted 0 ms 0 KB -