Submission #568556

#	Time	Username	Problem	Language	Result	Execution time	Memory
568556		piOOE	New Home (APIO18_new_home)	C++17	100 / 100	3784 ms	178932 KiB

new_home

//#define _GLIBCXX_DEBUG
 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include <bits/stdc++.h>
 
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
template<typename T>
using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template<typename T>
using normal_queue = priority_queue <T, vector<T>, greater<>>;
 
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
 
#define ll long long
#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) - begin(x))
#define ld long double
#define sz(s) ((int) size(s))
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define int128 __int128
#define pb push_back
#define eb emplace_back
 
 
template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
 
template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
 
int bit(int x, int b) {
    return (x >> b) & 1;
}
 
int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
 
//soryan za musor sverhu
 
const ll infL = 3e18;
const int infI = 1000000000 + 7;
const int infM = 2139062143;
const int N = 500001;
const int mod = 1e9 + 7;
const ld eps = 1e-9;
 
#define int ll
 
template<typename T>
struct SegTreeDownMax {
    const T MIN = numeric_limits<T>::min() / 2;
    vector <T> t;
    int sz;
 
    void init(int n, T x = numeric_limits<T>::min() / 2) {
        sz = n;
        t.assign(sz << 1, x);
    }
 
    void st(int i, T v) {
        int x = i + sz;
        t[x] = v;
        x >>= 1;
        while (x) {
            t[x] = max(t[x << 1], t[x << 1 | 1]);
            x >>= 1;
        }
    }
 
    T get(int l, int r) {
        l += sz;
        r += sz;
        // [l, r)
        T ans = MIN;
        while (l < r) {
            if (l & 1) {
                //it is a right child
                ckmx(ans, t[l++]);
            }
            if (r & 1) {
                //this is a left child
                ckmx(ans, t[--r]);
            }
            l >>= 1;
            r >>= 1;
        }
        return ans;
    }
 
};
 
template<typename T>
struct SegTreeDownMin {
    const T MAX = numeric_limits<T>::max() / 2;
    vector <T> t;
    int sz;
 
    void init(int n, T x = numeric_limits<T>::max() / 2) {
        sz = n;
        t.assign(sz << 1, x);
    }
 
    void st(int i, T v) {
        int x = i + sz;
        t[x] = v;
        x >>= 1;
        while (x) {
            t[x] = min(t[x << 1], t[x << 1 | 1]);
            x >>= 1;
        }
    }
 
    T get(int l, int r) { // [l, r)
        T ans = MAX;
        l += sz;
        r += sz;
        while (l < r) {
            if (l & 1) {
                //it is a right child
                ckmn(ans, t[l++]);
            }
            if (r & 1) {
                //this is a left child
                ckmn(ans, t[--r]);
            }
            l >>= 1;
            r >>= 1;
        }
        return ans;
    }
 
};
 
struct Q {
    int x, t, i, type;
 
    Q(int a, int b, int c, int d) {
        x = a, t = b, i = c, type = d;
    }
 
    Q() = default;
 
};
 
bool cmp(Q a, Q b) {
    if (a.t != b.t) return a.t < b.t;
    return a.type < b.type;
}
 
int x[N], a[N], b[N], t[N];
int X[N], T[N], cnt[N];
multiset<int> g[N];
ll ans[N];
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, q;
    cin >> n >> k >> q;
    vector<Q> v;
 
    vector<array<int, 4>> yy;
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        --t[i];
        v.emplace_back(x[i], b[i], i, 1);
        v.eb(x[i], a[i], i, -1);
    }
    for (int i = 0; i < q; ++i) {
        cin >> X[i] >> T[i];
        yy.pb({X[i], -1, -1, -1});
        v.eb(X[i], T[i], i, 0);
    }
 
    SegTreeDownMax<ll> stx;
    SegTreeDownMin<ll> stm;
    multiset<ll> L, R;
    auto dod = [&](int l, int r, int i) {
        int mid = (l + r) >> 1;
        yy.pb({mid, l, r, i});
    };
 
    auto find = [&](int x, int type) -> int {
        array nw = {x, type, -1ll, -1ll};
        return lower_bound(all(yy), nw) - begin(yy);
    };
    auto add = [&](int l, int r, int i) {
        int MMid = (l + r) >> 1;
        array nw = {MMid, l, r, i};
        int mid = lower_bound(all(yy), nw) - begin(yy);
        stx.st(mid, r);
        stm.st(mid, l);
    };
 
    auto del = [&](int l, int r, int i) {
        int MMid = (l + r) >> 1;
        array nw = {MMid, l, r, i};
        int mid = lower_bound(all(yy), nw) - begin(yy);
        stm.st(mid, stm.MAX);
        stx.st(mid, stx.MIN);
    };
 
    auto addR = [&](int x, int i) {
        R.insert(x);
    };
 
    auto delR = [&](int x, int i) {
        R.extract(x);
    };
    auto addL = [&](int x, int i) {
        L.insert(x);
    };
 
    auto delL = [&](int x, int i) {
        L.extract(x);
    };
    sort(all(v), cmp);
    {
        int num = 0;
        for (auto to: v) {
            if (to.type == -1) {
                int i = to.i;
                auto it = g[t[i]].upper_bound(x[i]);
                if (it != end(g[t[i]])) {
                    dod(x[i], *it, t[i]);
                }
                if (it != begin(g[t[i]])) {
                    it = prev(it);
                    dod(*it, x[i], t[i]);
                }
                g[t[i]].insert(x[i]);
                ++cnt[t[i]];
                assert(sz(g[t[i]]) == cnt[t[i]]);
            } else if (to.type == 1) {
                int i = to.i;
                auto it = g[t[i]].find(x[i]);
                assert(it != end(g[t[i]]));
                if (it != begin(g[t[i]]) && it != prev(end(g[t[i]]))) {
                    dod(*prev(it), *next(it), t[i]);
                }
                g[t[i]].erase(it);
                --cnt[t[i]];
                assert(sz(g[t[i]]) == cnt[t[i]]);
            }
        }
    }
    for (int i = 0; i < k; ++i) {
        if (!g[i].empty()) {
            assert(cnt[i]);
            exit(1);
        }
        assert(g[i].empty());
    }
    assert(*max_element(all(cnt)) == 0);
    sort(all(yy));
    uniq(yy);
    stm.init(sz(yy));
    stx.init(sz(yy));
    {
        int num = 0;
        for (auto to: v) {
            if (to.type == -1) {
                int i = to.i;
//                for (int z : g[t[i]]) cout << z << " ";
//                cout << endl;
                auto &st = g[t[i]];
                auto it = st.upper_bound(x[i]);
//                if (it != end(g[t[i]])) {
//                    trace(*it)
//                }
                if (it != begin(g[t[i]]) && it != end(g[t[i]])) {
                    del(*prev(it), *it, t[i]);
                }
                if (it != end(st)) {
                    add(x[i], *it, t[i]);
                } else {
                    if (!st.empty()) {
                        delR(*st.rbegin(), t[i]);
                    }
                    addR(x[i], t[i]);
                }
                if (it != begin(g[t[i]])) {
                    it = prev(it);
                    add(*it, x[i], t[i]);
                } else {
                    if (!st.empty()) {
                        delL(*begin(st), t[i]);
                    }
                    addL(x[i], t[i]);
                }
                g[t[i]].insert(x[i]);
                if (cnt[t[i]] == 0) ++num;
                ++cnt[t[i]];
            } else if (to.type == 1) {
                int i = to.i;
                auto &st = g[t[i]];
                auto it = g[t[i]].find(x[i]);
                assert(it != end(g[t[i]]));
                if (it == prev(end(st))) {
                    delR(x[i], t[i]);
                    if (sz(st) != 1) {
                        del(*prev(it), x[i], t[i]);
                        addR(*prev(it), t[i]);
                    }
                }
                if (it == begin(st)) {
                    delL(x[i], t[i]);
                    if (sz(st) != 1) {
                        del(x[i], *next(it), t[i]);
                        addL(*next(it), t[i]);
                    }
                }
                if (it != begin(st) && it != prev(end(st))){
                    del(x[i], *next(it), t[i]);
                    del(*prev(it), x[i], t[i]);
                    add(*prev(it), *next(it), t[i]);
                }
                g[t[i]].erase(it);
                --cnt[t[i]];
                if (cnt[t[i]] == 0) --num;
            } else {
                int i = to.i;
                if (num != k) {
                    ans[i] = -1;
                } else {
                    int id = find(X[i], -1);
//                    trace(yy[id][0])
//                    trace(X[i] - stm.get(id, stx.sz))
//                    trace(stx.get(0, id) - X[i])
//                    trace(X[i] - *begin(R));
//                    trace(*rbegin(L) - X[i])
//                    assert(!L.empty());
//                    assert(!R.empty());
//                    trace(id)
                    ans[i] = max({X[i] - stm.get(id, stx.sz), stx.get(0, id) - X[i], X[i] - *begin(R), *rbegin(L) - X[i]});
                    assert(ans[i] <= 100000000 && ans[i] >= 0);
                }
            }
        }
    }
    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:242:13: warning: unused variable 'num' [-Wunused-variable]
  242 |         int num = 0;
      |             ^~~

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