Submission #1165884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165884		turska	새 집 (APIO18_new_home)	C++20	5 / 100	728 ms	239452 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define all(v) (v).begin(), (v).end()

#define ff first
#define ss second

const int INF = 1e9;
const int mxN = 3e5;

struct cc: vector<int> {
    using vector<int>::vector;
    void fix() {
        sort(all(*this));
        erase(unique(all(*this)), end());
    }
    // a[i]>=x
    int gte(int x) {         
        return lower_bound(all(*this), x)-begin(); 
    }
    // a[i]>x
    int gt(int x) {
        return upper_bound(all(*this), x)-begin();
    }
    // a[i]<=x
    int lte(int x) {
        return gt(x)-1;
    }
    // a[i]<x
    int lt(int x) { 
        return gte(x)-1;
    }
};


array<int, 4> stores[mxN];
array<int, 2> queries[mxN];
int ans[mxN];
vector<array<int, 3>> t[12*mxN]; // (a, b, is_query)
// for query a=pos, b=id
int N, K, Q;

cc times, pos;
// store cc id in segtree

template <class S, S (*op)(S, S), S e>
struct segtree {
    int sz;
    vector<int> t, saves;
    vector<pair<int&, int>> hist;
    segtree() { }
    void init(int n) { 
        t.assign(4*n, e);
        sz = n;
    };
    int get(int v, int tl, int tr, int pos) {
        if (tl==tr) return t[v];
        int tm = (tl+tr)/2;
        if (pos<=tm) return op(t[v], get(v*2, tl, tm, pos));
        else return op(t[v], get(v*2+1, tm+1, tr, pos));
    }
    int get(int pos) { return get(1, 0, sz-1, pos); }
    void update(int v, int tl, int tr, int l, int r, int val) {
        if (r<tl || tr<l) return;
        if (l<=tl && tr<=r) {
            hist.push_back({t[v], t[v]});
            t[v] = op(t[v], val);
            return;
        }
        int tm = (tl+tr)/2;
        update(v*2, tl, tm, l, r, val);
        update(v*2+1, tm+1, tr, l, r, val);
    }
    void update(int l, int r, int val) { update(1, 0, sz-1, l, r, val); }

    void save() {
        saves.push_back(hist.size());
    };
    void rollback() {
        while (hist.size()>saves.back()) {
            t[hist.back().ff] = hist.back().ss;
            hist.pop_back();
        }
        saves.pop_back();
    }
};
int op_mn(int a, int b) {return min(a, b); }
int op_mx(int a, int b) {return max(a, b); }
segtree<int, op_mn, INF> st_left;
segtree<int, op_mx, 0> st_right;

void update(int v, int tl, int tr, int l, int r, array<int, 3> a) {
    if (tr<l || r<tl) return;
    if (l<=tl && tr<=r) {
        t[v].push_back(a);
        return;
    }
    int tm = (tl+tr)/2;
    update(v*2, tl, tm, l, r, a);
    update(v*2+1, tm+1, tr, l, r, a);
};
void update(int l, int r, array<int, 3> a) { update(1, 0, times.size()-1, l, r, a); }
multiset<int> cur_stores;
void dfs(int v, int tl, int tr) {

}

void brute( ) {
    for (int i=0; i<Q; i++) {
        auto [l, y] = queries[i];
        vector<set<int>> pos(K);
        for (int i=0;i <N; i++) {
            auto [x, t, a, b] = stores[i];
            if (y<a || b<y) continue;
            pos[t].insert(x);
        }
        int d = 0;
        for (int i=0; i<K; i++) {
            if (pos[i].empty()) {
                d = -1;
                break;
            }
            int cur = INF;
            auto it = pos[i].lower_bound(l);
            if (it!=pos[i].end()) cur = min(cur, *it-l);
            if (it!=pos[i].begin()) cur = min(cur, l-*(--it));
            d = max(d, cur);
        }
        cout << d << '\n';
    }
}




void solve() {
    cin >> N >> K >> Q;
    pos.push_back(0);
    for (int i=0; i<N; i++) {
        for (int j=0; j<4; j++) cin >> stores[i][j];
        stores[i][1]--;
        pos.push_back(stores[i][0]);
    }
    for (int i=0; i<Q; i++) {
        cin >> queries[i][0] >> queries[i][1];
        pos.push_back(stores[i][0]);
        times.push_back(queries[i][1]);
    }
    if (N<=400 && Q<=400) {
        brute();
        return;
    }
    // case when 0 bad bad bad
    pos.fix();
    times.fix();
    st_left.init(pos.size());
    st_right.init(pos.size());
    for (int i=0; i<pos.size(); i++) {
        st_left.update(i, i, i);
        st_right.update(i, i, i);
    }
    bool bad = false;
    vector<vector<int>> store_pos(K);
    for (int i=0; i<N; i++) {
        auto [a, b, y, x] = stores[i];
        store_pos[b].push_back(pos.gte(a));
    }
    for (int i=0; i<K; i++) sort(all(store_pos[i]));
    for (int k=0; k<K; k++) {
        bad |= store_pos[k].empty();
        if (store_pos[k].empty()) continue; 

        st_right.update(0, store_pos[k][0], store_pos[k][0]);
        st_left.update(store_pos[k].back(), pos.size()-1, store_pos[k].back());

        for (int i=0; i+1<store_pos[k].size(); i++) {
            int a = store_pos[k][i];
            int b = store_pos[k][i+1];
            int m = pos.gte((pos[a]+pos[b])/2);
            st_left.update(a, m-1, a);
            st_right.update(m, b, b);
        }
    }
    for (int i=0; i<Q; i++) {
        if (bad) cout << "-1\n";
        else {
            int l = queries[i][0];
            int j = pos.gte(l);
            cout << max(l-pos[st_left.get(j)], pos[st_right.get(j)]-l) << '\n';
        }
    }

    /*for (int i=0; i<N; i++) {*/
    /*    update(times.gte(stores[i][2]), times.lte(stores[i][3]), {pos.gte(stores[i][0]), stores[i][1], 0});*/
    /*}*/
    /*for (int i=0; i<Q; i++) {*/
    /*    update(times.gte(queries[i][1]), times.gte(queries[i][1]), {pos.gte(queries[i][0]), i, 1});*/
    /*}*/
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc = 1;
    /*cin >> tc;*/
    while (tc--) solve();
}

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