답안 #743557

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
743557 2023-05-17T13:44:19 Z alvingogo 새 집 (APIO18_new_home) C++14
10 / 100
447 ms 65108 KB
#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;
}
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 Grader output
1 Incorrect 365 ms 46048 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -