Submission #1033451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033451		_8_8_	New Home (APIO18_new_home)	C++17	100 / 100	4458 ms	384912 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];

vector<int> pts;
multiset<int> bf[N * 4];
int m;
int T[N * 4];
void upd(int pos,int val,bool ok,int v = 1,int tl = 0,int tr = m){
    if(tl == tr){
        if(ok) bf[v].insert(val);
        else bf[v].erase(bf[v].find(val));
        T[v] = (bf[v].empty() ? 0 : *bf[v].rbegin()); 
        // cout << tl << ' ' << val << "f\n";
    }else{
        int tm = (tl + tr) >> 1;
        if(pos <= tm) upd(pos,val,ok,v+v,tl,tm);
        else upd(pos,val,ok,v+v+1,tm+1,tr);
        T[v] = max(T[v + v],T[v + v + 1]);
    }
}
int get(int l,int r,int v = 1,int tl = 0,int tr = m){
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) return T[v];
    int tm = (tl + tr) >> 1;
    return max(get(l,r,v+v,tl,tm),get(l,r,v+v+1,tm+1,tr));
}
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 l,int r){
    int k = lower_bound(pts.begin(),pts.end(),l) - pts.begin();
    // cout << l << ' ' << r << ' ' << k << '\n';
    upd(k,r,1);
}
void _del(int l,int r){
    int k = lower_bound(pts.begin(),pts.end(),l) - pts.begin();
    upd(k,r,0);
}
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});_add(L+1,x-1);
    cur.insert({x + 1,R - 1});_add(x+1,R-1);
    cur.erase(cur.find({L + 1,R - 1}));_del(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}));_del(L+1,x-1);
    cur.erase(cur.find({x + 1,R - 1}));_del(x+1,R-1);
    cur.insert({L + 1,R - 1});_add(L+1,R-1);
    st[i].erase(st[i].find(x));
}
int res[N];
bool ok(int l,int r){
    int k = upper_bound(pts.begin(),pts.end(),l) - pts.begin() - 1;
    // cout << l << ' ' << k << ' ' << get(0,k) << ' ' << r << "\n";
    if(get(0,k) >= 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];
        pts.push_back(x[i] + 1);
        pts.push_back(x[i] - 1);
        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);
    }
    pts.push_back(1);
    pts.push_back((int)1e9);
    sort(pts.begin(),pts.end());
    pts.resize(unique(pts.begin(),pts.end()) - pts.begin());
    m = (int)pts.size() - 1;
    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);
        _add(1,inf);
        cur.insert({1,inf});
    }
    for(Q d:s) {
        if(d.tp == 0) {
            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;
            }
            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: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20