Submission #1279745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279745		enxiayy	New Home (APIO18_new_home)	C++20	100 / 100	2635 ms	127460 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

#define REP(i, l, r) for(int i = (l); i < (r); ++i)
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)
#define ff first
#define ss second
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), v.end())
#define dbg(v) "[" #v " = " << (v) << "]"
#define el "\n"

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;

template<class T> bool minimize(T& a, const T& b){ if(a > b) return a = b, true; return false; } 
template<class T> bool maximize(T& a, const T& b){ if(a < b) return a = b, true; return false; } 
template<class T> int lwb(vector<T> &a, T& b) { return lower_bound(all(a), b) - a.begin(); }

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long randRange(long long l, long long r){ return uniform_int_distribution<long long>(l,r)(rng); }

const int N = 3e5 + 5;
const int INF = 1e9;

struct event {
    int type, x, time, id;
    event(int type = 0, int x = 0, int time = 0, int id = 0) : type(type), x(x), time(time), id(id) {}
};
vector<event> events;
vector<int> compress;
multiset<int> save[N];
multiset<int> nxt_pos[N];
int ans[N];
struct IT {
    vector<ll> st;
    int n;

    IT(int n) : n(n), st(4 * n + 5) {}

    void update(int id, int l, int r, int pos, ll val) {
        if (l > pos || r < pos)
            return;
        if (l == r) {
            st[id] = val;
            return;
        }

        int mid = (l + r) >> 1;
        update(id << 1, l, mid, pos, val);
        update(id << 1 | 1, mid + 1, r, pos, val);

        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }

    ll get(int id, int l, int r, int u, int v) {
        if (l > v || r < u)
            return -INF;
        if (u <= l && r <= v)
            return st[id];

        int mid = (l + r) >> 1;
        return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }

    void update(int pos) {
        ll val = 0;
        if (!nxt_pos[pos].empty()) val = *(nxt_pos[pos].rbegin());
        update(1, 1, n, pos, val);
    }

    ll query(int l, int r) {
        if (l > r) return -INF;
        return get(1, 1, n, l, r);
    }
};
int n, k, q;

void solve() {
    cin >> n >> k >> q;
    FOR(i, 1, n) {
        int x, t, l, r;
        cin >> x >> t >> l >> r;
        events.eb(0, x, l, t);
        events.eb(1, x, r + 1, t);
        compress.eb(x);
    }

    FOR(i, 1, q) {
        int x, t;
        cin >> x >> t;
        events.eb(2, x, t, i);
    }

    compress.eb(-INF);
    compress.eb(INF);

    sort(all(compress));
    compact(compress);

    sort(all(events), [&](event u, event v) {
        if (u.time == v.time) return u.type < v.type;
        else return u.time < v.time;
    });

    

    FOR(i, 1, k) {
        save[i].insert(-INF); save[i].insert(INF);
        nxt_pos[1].insert(INF);
    }

    IT st(sz(compress));
    st.update(1);

    auto add = [&](int l, int r) -> void {
        l = lwb(compress, l) + 1;
        nxt_pos[l].insert(r);
        st.update(l);
    };

    auto del = [&](int l, int r) -> void {
        l = lwb(compress, l) + 1;
        nxt_pos[l].erase(nxt_pos[l].find(r));
        st.update(l);
    };

    auto update = [&](int type, int x, int id) -> void {
        // cerr << (type == 0 ? "add" : "del") << el;

        if (type == 0) { // add
            save[id].insert(x);
            int prv = -INF;
            int nxt = INF;
            auto it = save[id].lower_bound(x);
            if (next(it) != save[id].end()) nxt = *(next(it));
            if (it != save[id].begin()) prv = *(prev(it));
            // cerr << prv << " " << nxt << el;
            del(prv, nxt);
            add(prv, x);
            add(x, nxt);
        }
        else { // del
            int prv = -INF;
            int nxt = INF;
            auto it = save[id].lower_bound(x);
            if (next(it) != save[id].end()) nxt = *(next(it));
            if (it != save[id].begin()) prv = *(prev(it));
            save[id].erase(it);
            // cerr << prv << " " << nxt << el;
            del(prv, x);
            // cerr << "ok" << el;
            del(x, nxt);
            add(prv, nxt);
        }
    };

    auto query = [&](int x) -> int {
        int l = 0;
        int r = 1e8;
        int ans = -1;
        while(l <= r) {
            int mid = (l + r) >> 1;
            int bound_left = max(1, x - mid);
            int bound_right = min(100000000, x + mid);
            bound_left = lwb(compress, bound_left) + 1;
            if (st.query(1, bound_left - 1) <= bound_right) {
                ans = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        return ans;
    };

    for(auto [type, x, time, id] : events) {
        // cerr << type << ": " << x << " " << id << el;
        if (type != 2) {
            update(type, x, id);
        }
        else {
            ans[id] = query(x);
        }
    }

    FOR(i, 1, q) cout << ans[i] << el;

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    #define task "task" 
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    solve();

    return 0;
}

/*

*/

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:207:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:208:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  208 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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