Submission #1033441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033441		_8_8_	New Home (APIO18_new_home)	C++17	5 / 100	5104 ms	120036 KiB

new_home

#include <bits/stdc++.h>
 
using namespace std;
    
typedef long long ll;
const int  N = 1e6 + 21, MOD = (int)1e9+7;
 
int n,k,q,x[N],t[N],a[N],b[N];
struct Q{
    int tp,y,x,v,id;
};
multiset<int> st[N];
vector<Q> s;
bool cmp(Q l,Q r){
    if(l.y != r.y)
        return l.y < r.y;
    return l.tp < r.tp;
}
multiset<pair<int,int>> cur;
void add(int i,int x){
    // cerr << (int)st[i].size() << "x\n";
    auto it = st[i].lower_bound(x);
    int R = *it,L;
    --it;
    L =*it;
    cur.insert({L+1,x - 1});
    cur.insert({x + 1,R - 1});
    cur.erase(cur.find({L + 1,R - 1}));
    st[i].insert(x);
    // cerr << (int)st[i].size() << "x\n";
}
void del(int i,int x){
    auto it = st[i].lower_bound(x);
    it++;
    int R = *it,L;
    --it;--it;
    L =*it;
    cur.erase(cur.find({L + 1,x - 1}));
    cur.erase(cur.find({x + 1,R - 1}));
    cur.insert({L + 1,R - 1});
    st[i].erase(st[i].find(x));
}
int res[N];
bool ok(int l,int r){
    for(auto [L,R]:cur){
        if(L <= l && R >= r) return false;
    }
    return true;
}
void test() {
    cin >> n >> k >> q;
    for(int i = 1;i <= n;++i){
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        Q f,_f;
        f.y = a[i];f.tp = 0;f.v = t[i];f.x = x[i];
        s.push_back(f);
        _f.y = b[i];_f.tp = 2;_f.v = t[i];_f.x = x[i];
        s.push_back(_f);
    }
    for(int i = 1;i <= q;i++){
        int l,y;
        cin >> l >> y;
        Q a;
        a.tp = 1;
        a.id = i;
        a.x = l;
        a.y = y;
        s.push_back(a);
    }
    sort(s.begin(),s.end(),cmp);
    const int inf = (int)1e9;
    for(int i = 1;i <= k;i++) {
        st[i].insert(0);
        st[i].insert((int)1e9 + 1);
        cur.insert({1,inf});
    }
    for(Q d:s) {
        if(d.tp == 0) {
            // cout << d.v << ' ' << d.x << '\n';
            add(d.v,d.x);
        }else if(d.tp == 2) {
            del(d.v,d.x);
        }else{
            if(cur.find({1,(int)1e9}) != cur.end()) {
                res[d.id] = -1;
                continue;
            }
            // continue;
            int l = -1,r = (int)1e9;
            while(r - l > 1){
                int mid = (l + r) >> 1;
                if(ok(max(1,d.x - mid),d.x + mid)){
                    r = mid;
                }else{
                    l = mid;
                }
            }
            res[d.id] = r;
        }
    }
    for(int i = 1;i <= q;++i) {
        cout << res[i] << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20