제출 #1167129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167129		thdh__	새 집 (APIO18_new_home)	C++20	70 / 100	3970 ms	1054848 KiB

new_home

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fu(x,a,b) for (auto x=a;x<=b;x++)
#define fd(x,a,b) for (auto x=a;x>=b;x--)
#define int ll

using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

typedef pair<int, int> ii;
const int N = 2e6+5;
const int mod = 1e9+7;
const int inf = 2e8;
using cd = complex<double>;
const long double PI = acos(-1);
int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} 

struct leaf {
    static leaf mem[];
    static int cnt;

    multiset<int> leaf_min = {}, leaf_max = {};
};

leaf leaf::mem[N];
int leaf::cnt = 0;

struct vertex {

    vertex *l = nullptr, *r = nullptr;
    int minv = inf, maxv = -inf;

    int lf = 0;

    void extend() {
        if (!l) {
            l = new vertex;
            r = new vertex;
        }
    }

    int query_min(int tl, int tr, int lv, int rv) {
        if (lv >= rv)
            return inf;
        if (lv == tl && rv == tr)
            return minv;
        int tm = (tl + tr) / 2;
        extend();
        return min(
            l->query_min(tl, tm, lv, min(tm, rv)),
            r->query_min(tm, tr, max(lv, tm), rv)
        );
    }

    int query_max(int tl, int tr, int lv, int rv) {
        if (lv >= rv)
            return -inf;
        if (lv == tl && rv == tr)
            return maxv;
        int tm = (tl + tr) / 2;
        extend();
        return max(
            l->query_max(tl, tm, lv, min(tm, rv)),
            r->query_max(tm, tr, max(lv, tm), rv)
        );
    }

    void update(int tl, int tr, int lv, int rv, bool add) {
        if (tl + 1 == tr) {
            if (!lf)
                lf = ++leaf::cnt;
            multiset<int> &mins = leaf::mem[lf].leaf_min;
            multiset<int> &maxs = leaf::mem[lf].leaf_max;
            if (add)
                mins.insert(lv), maxs.insert(rv);
            else
                mins.erase(mins.find(lv)), maxs.erase(maxs.find(rv));
            minv = mins.empty() ? inf : *mins.begin();
            maxv = maxs.empty() ? -inf : *maxs.rbegin();
        }
        else {
            int tm = (tl + tr) / 2;
            extend();
            if ((lv + rv) / 2 < tm)
                l->update(tl, tm, lv, rv, add);
            else
                r->update(tm, tr, lv, rv, add);
            minv = min(l->minv, r->minv);
            maxv = max(l->maxv, r->maxv);
        }
    }
};

int n,k,q;
vector<array<int,4>> p;
int ans[N];

void solve()
{
	cin>>n>>k>>q;
    for (int i = 1; i <= n; i++) 
    {
        int x,t,a,b;
        cin>>x>>t>>a>>b; --t;
        p.pb({a, 0, x, t}); // 0 = add
        p.pb({b+1, 1, x, t}); // 1 = delete
    }
    for (int i = 1; i <= q; i++)
    {
        int l,y;
        cin>>l>>y;
        p.pb({y, 2, l, i}); // 2 = query
    }
    sort(all(p));
    vector<multiset<int>> s(k, {-inf, inf});
    vertex st;
    for (int i = 0; i < k; i++) st.update(-inf,inf,-inf,inf,1);
    int cnt = 0;
    for (auto i : p) 
    {
        int type = i[1];
        if (!type) 
        {
            int t = i[3], x = i[2];
            auto it = s[t].upper_bound(x);
            int nxt = *it, prv = *--it;
            st.update(-inf,inf,prv,nxt,0);
            st.update(-inf,inf,prv,x,1);
            st.update(-inf,inf,x,nxt,1);
            if (s[t].size() == 2) cnt++;
            s[t].insert(x);
        } else if (type == 1) 
        {
            int t = i[3], x = i[2];
            auto it = s[t].find(x);
            int nxt = *next(it,1), prv = *prev(it,1);
            st.update(-inf,inf,prv,x,0);
            st.update(-inf,inf,x,nxt,0);
            st.update(-inf,inf,prv,nxt,1);
            s[t].erase(it);
            if (s[t].size() == 2) cnt--;
        } else 
        {
            int l = i[2], t = i[3];
            if (cnt < k) ans[t] = -1;
            else ans[t] =  max(l - st.query_min(-inf, inf, l, inf), st.query_max(-inf, inf, -inf, l) - l);
        }
    }
    for (int i = 1; i <= q; i++) cout<<ans[i]<<endl;
}

signed main()
{
	bruh
	//freopen("input.inp","r",stdin);
	//freopen("output.inp","w",stdout);
	int t = 1;
	// cin>>t;
	while (t--)
	{
		solve();
		cout<<"\n";
	}
}

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