Submission #1100189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100189		vladilius	New Home (APIO18_new_home)	C++17	0 / 100	5083 ms	223416 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 1e8;

struct IT{
    struct node{
        node *l, *r;
        int m;
        node(){
            l = r = 0;
            m = 0;
        }
    };
    multiset<int> r1;
    map<pii, vector<int>> pp;
    map<int, int> mp;
    set<int> p;
    vector<int> all;
    vector<int> :: iterator it;
    node *rt;
    int n;
    void init(vector<int> all1){
        rt = new node();
        all = all1;
        n = (int) all.size();
        int i = 0;
        while (i < all.size()){
            int j = i;
            while (j < all.size() && all[i] == all[j]){
                j++;
            }
            mp[all[i]] = i + 1;
            i = j;
        }
        for (int i = 1; i <= n; i++) p.insert(i);
    }
    void upd(node *v, int tl, int tr, int& p, int& x){
        if (tl == tr){
            v -> m = x;
            return;
        }
        int tm = (tl + tr) / 2;
        if (p <= tm){
            if (!(v -> l)) v -> l = new node();
            upd(v -> l, tl, tm, p, x);
        }
        else {
            if (!(v -> r)) v -> r = new node();
            upd(v -> r, tm + 1, tr, p, x);
        }
        v -> m = 0;
        if (v -> l) v -> m = max(v -> m, v -> l -> m);
        if (v -> r) v -> m = max(v -> m, v -> r -> m);
    }
    void add(int l, int r){
        if (l == 1){
            r1.insert(r);
            return;
        }
        auto it = p.lower_bound(mp[l - 1]);
        pp[{l, r}].pb((*it));
        l = (*it);
        upd(rt, 1, n, l, r);
        p.erase(it);
    }
    void rem(int l, int r){
        if (l == 1){
            r1.erase(r1.find(r));
            return;
        }
        auto it = pp.find({l, r});
        l = (*it).ss.back(); r = 0;
        upd(rt, 1, n, l, r);
        p.insert(l);
        pp[{l, r}].pop_back();
    }
    int get(node *v, int tl, int tr, int l, int r){
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return v -> m;
        int tm = (tl + tr) / 2, out = 0;
        if (v -> l) out = max(out, get(v -> l, tl, tm, l, r));
        if (v -> r) out = max(out, get(v -> r, tm + 1, tr, l, r));
        return out;
    }
    bool get(int l, int r){
        if (!r1.empty() && *prev(r1.end()) >= r) return 1;
        it = lower_bound(all.begin(), all.end(), l);
        if (it == all.begin()) return 0;
        l = (int) (it - all.begin());
        return get(rt, 1, n, 1, l) >= r;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, k, q; cin>>n>>k>>q;
    vector<int> x(n + 1), t(n + 1), a(n + 1), b(n + 1), all;
    mt19937 rng((int) time(0));
    for (int i = 1; i <= n; i++){
        cin>>x[i]>>t[i]>>a[i]>>b[i];
        all.pb(x[i]);
    }
    vector<int> xq(q + 1), yq(q + 1);
    for (int i = 1; i <= q; i++){
        cin>>xq[i]>>yq[i];
    }
    
    sort(all.begin(), all.end());

    map<int, vector<pii>> mp;
    for (int i = 1; i <= n; i++){
        mp[a[i]].pb({1, i});
        mp[b[i] + 1].pb({2, i});
    }
    for (int i = 1; i <= q; i++){
        mp[yq[i]].pb({i + 2, xq[i]});
    }
    
    vector<int> out(q + 1), cnt(k + 1);
    multiset<int> st[k + 1];
    map<int, int> cc;
    int df = 0, l, r;
    vector<pii> qq;
    IT T; T.init(all);
    for (auto [X, V]: mp){
        qq.clear();
        for (auto [tt, i]: V){
            if (tt == 1){
                df += !cnt[t[i]];
                cnt[t[i]]++;
                if (st[t[i]].empty()){
                    if (1 < x[i]) T.add(1, x[i] - 1);
                    if (x[i] < inf) T.add(x[i] + 1, inf);
                    st[t[i]].insert(x[i]);
                    continue;
                }
                
                if (st[t[i]].find(x[i]) != st[t[i]].end()){
                    st[t[i]].insert(x[i]);
                    continue;
                }
                
                auto it = st[t[i]].upper_bound(x[i]);
                if (it == st[t[i]].end()) r = inf;
                else r = (*it) - 1;
                if (it == st[t[i]].begin()) l = 1;
                else l = *prev(it) + 1;
                
                if (l <= r) T.rem(l, r);
                if (l < x[i]) T.add(l, x[i] - 1);
                if (x[i] < r) T.add(x[i] + 1, r);
                
                st[t[i]].insert(x[i]);
            }
            else if (tt == 2){
                cnt[t[i]]--;
                df -= !cnt[t[i]];
                
                if (st[t[i]].count(x[i]) > 1){
                    st[t[i]].erase(st[t[i]].find(x[i]));
                    continue;
                }
                
                auto it = st[t[i]].find(x[i]);
                
                if (it == st[t[i]].begin()) l = 1;
                else l = *prev(it) + 1;
                if (it == prev(st[t[i]].end())) r = inf;
                else r = *next(it) - 1;
                
                if (l < x[i]) T.rem(l, x[i] - 1);
                if (x[i] < r) T.rem(x[i] + 1, r);
                
                if (cnt[t[i]]) T.add(l, r);
                st[t[i]].erase(it);
            }
            else {
                qq.pb({tt - 2, i});
            }
        }
        for (auto [ii, x]: qq){
            if (df < k){
                out[ii] = -1;
                continue;
            }
            
            auto check = [&](int d){
                return T.get(max(1, x - d), min(inf, x + d));
            };
            
            int l = 0, r = inf;
            while (l + 1 < r){
                int m = (l + r) / 2;
                if (check(m)){
                    l = m + 1;
                }
                else {
                    r = m;
                }
            }
            if (check(l)) l = r;
            
            out[ii] = l;
        }
    }
    
    for (int i = 1; i <= q; i++){
        cout<<out[i]<<"\n";
    }
}

Compilation message (stderr)

new_home.cpp: In member function 'void IT::init(std::vector<int>)':
new_home.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         while (i < all.size()){
      |                ~~^~~~~~~~~~~~
new_home.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |             while (j < all.size() && all[i] == all[j]){
      |                    ~~^~~~~~~~~~~~

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