Submission #743557

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743557	2023-05-17T13:44:19 Z	alvingogo	New Home (APIO18_new_home)	C++14	10 / 100	447 ms	65108 KB

new_home

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

typedef pair<int,int> pii;
signed main(){
    AquA;
    int n,k,q;
    cin >> n >> k >> q;
    vector<pair<pii,pii> > vp(n);
    vector<pii> g;
    for(int i=0;i<n;i++){
        cin >> vp[i].fs.fs >> vp[i].fs.sc >> vp[i].sc.fs >> vp[i].sc.sc;
        vp[i].fs.sc--;
        g.push_back({vp[i].fs.fs,vp[i].fs.sc});
    }
    sort(g.begin(),g.end());
    vector<pii> sl;
    vector<int> s(k,-1);
    multiset<int> ms;
    vector<pair<int,pii> > eve;
    for(auto h:g){
        if(s[h.sc]==-1){
            ms.insert(h.fs);
        }    
        else{
            eve.push_back({(s[h.sc]+h.fs+1)/2,{s[h.sc],h.fs}});
        }
        s[h.sc]=h.fs;
    }
    for(int i=0;i<k;i++){
        if(s[i]==-1){
            for(int j=0;j<q;j++){
                cout << -1 << "\n";
            }
            return 0;
        }
    }
    vector<int> ans(q+1);
    for(int i=1;i<=q;i++){
        int l,y;
        cin >> l >> y;
        eve.push_back({l,{-1,i}});
    }
    sort(eve.begin(),eve.end());
    vector<pii> ins,que;
    int nw=-1;
    for(auto t:eve){
        if(t.fs!=nw){
            for(auto h:ins){
                ms.erase(ms.find(h.fs));
                ms.insert(h.sc);
            }
            for(auto h:que){
                auto y=*ms.rbegin();
                auto z=*ms.begin();
                ans[h.sc]=max(abs(y-h.fs),abs(z-h.fs));
            }
            ins.clear();
            que.clear();
        }
        if(t.sc.fs<0){
            que.push_back({t.fs,t.sc.sc});
        }
        else{
            ins.push_back(t.sc);
        }
        nw=t.fs;
    }
    for(auto h:ins){
        ms.erase(ms.find(h.fs));
        ms.insert(h.sc);
    }
    for(auto h:que){
        auto y=*ms.rbegin();
        auto z=*ms.begin();
        ans[h.sc]=max(abs(y-h.fs),abs(z-h.fs));
    }
    for(int i=1;i<=q;i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Incorrect	1 ms	212 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Incorrect	1 ms	212 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	447 ms	48024 KB	Output is correct
2	Correct	319 ms	56548 KB	Output is correct
3	Correct	342 ms	65108 KB	Output is correct
4	Correct	403 ms	51740 KB	Output is correct
5	Correct	282 ms	56552 KB	Output is correct
6	Correct	326 ms	56512 KB	Output is correct
7	Correct	323 ms	65072 KB	Output is correct
8	Correct	442 ms	51952 KB	Output is correct
9	Correct	421 ms	59008 KB	Output is correct
10	Correct	353 ms	57084 KB	Output is correct
11	Correct	354 ms	56336 KB	Output is correct
12	Correct	334 ms	56780 KB	Output is correct