제출 #916031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916031		GrindMachine	새 집 (APIO18_new_home)	C++17	100 / 100	4354 ms	240776 KiB

new_home

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

sweep through time, answer queries offline
for a given query, do b.s
when mid is fixed, we get a range [l,r]
find if all types [1..k] are present in [l,r]

key idea:
at a given time, lets say for a given type of shop t, the active positions are p[1],p[2],...,p[m] 
then if [l,r] lies in any of the segs [1,p[1]-1],[p[1]+1,p[2]-1],[p[2]+1,p[3]-1],...,[p[m]+1,MAX(=1e8)], then [l,r] is bad
otherwise, [l,r] is good

checking this efficiently can be done with a range max segtree 
all ranges can be maintained efficiently with a multiset

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct segtree {
    // https://codeforces.com/blog/entry/18051

    /*=======================================================*/

    struct data {
        int a;
    };

    data neutral = {0};

    data merge(data &left, data &right) {
        data curr;
        curr.a = max(left.a,right.a);
        return curr;
    }

    void create(int i, T v) {

    }

    void modify(int i, T v) {
        tr[i].a = v;
    }

    /*=======================================================*/

    int n;
    vector<data> tr;

    segtree() {

    }

    segtree(int siz) {
        init(siz);
    }

    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }

    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    void pupd(int i, T v) {
        modify(i + n, v);
        for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    data query(int l, int r) {
        data resl = neutral, resr = neutral;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, tr[l++]);
            if (!(r & 1)) resr = merge(tr[r--], resr);
        }

        return merge(resl, resr);
    }
};

void solve(int test_case)
{
    int n,k,q; cin >> n >> k >> q;
    vector<array<int,4>> a(n+5);
    rep1(i,n) rep(j,4) cin >> a[i][j];
    vector<int> b;

    map<int,vector<array<int,3>>> mp;

    rep1(i,n){
        auto [x,t,l,r] = a[i];
        mp[l].pb({1,t,x});
        mp[r+1].pb({2,t,x});
        b.pb(x);
    }

    rep1(id,q){
        int x,y; cin >> x >> y;
        mp[y].pb({3,id,x});
        b.pb(x);        
    }

    b.pb(-inf1), b.pb(inf1);
    sort(all(b));
    b.resize(unique(all(b))-b.begin());
    int siz = sz(b);

    multiset<int> pos[k+5];
    multiset<int> ms[siz];
    segtree<int> st(siz);

    rep1(i,k){
        pos[i].insert(0), pos[i].insert(siz-1);
        ms[0].insert(siz-1);
    }

    st.pupd(0,siz-1);

    auto upd = [&](int op, int l, int r){
        if(op == 1){
            ms[l].insert(r);
            st.pupd(l,*ms[l].rbegin());
        }
        else{
            ms[l].erase(ms[l].find(r));
            if(ms[l].empty()){
                st.pupd(l,0);
            }
            else{
                st.pupd(l,*ms[l].rbegin());
            }
        }
    };

    auto add = [&](int t, int x){
        x = lower_bound(all(b),x)-b.begin();
        pos[t].insert(x);
        auto it = pos[t].find(x);
        int l = -1, r = -1;
        if(it != pos[t].begin()){
            l = *prev(it);
        }
        if(next(it) != pos[t].end()){
            r = *next(it);
        }

        assert(l != -1 and r != -1);

        upd(2,l,r);
        upd(1,l,x);
        upd(1,x,r);
    };

    auto rem = [&](int t, int x){
        x = lower_bound(all(b),x)-b.begin();
        auto it = pos[t].find(x);
        int l = -1, r = -1;
        if(it != pos[t].begin()){
            l = *prev(it);
        }
        if(next(it) != pos[t].end()){
            r = *next(it);
        }

        assert(l != -1 and r != -1);
        pos[t].erase(it);

        upd(2,l,x);
        upd(2,x,r);
        upd(1,l,r);
    };

    vector<int> ans(q+5,-1);

    for(auto [ti,v] : mp){
        for(auto [t,typ,x] : v){
            if(t == 1){
                add(typ,x);
            }
            else if(t == 2){
                rem(typ,x);
            }
            else{
                int id = typ;
                int lo = 0, hi = 1e8;
                while(lo <= hi){
                    int mid = (lo+hi) >> 1;
                    int ind = lower_bound(all(b),x-mid)-b.begin();
                    int mxr = st.query(0,ind-1).a;
                    if(b[mxr]-x <= mid){
                        ans[id] = mid;
                        hi = mid-1;
                    }
                    else{
                        lo = mid+1;
                    }
                }
            }
        }
    }

    rep1(i,q) cout << ans[i] << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 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