Submission #705585

#	Time	Username	Problem	Language	Result	Execution time	Memory
705585		noedit	New Home (APIO18_new_home)	C++17	100 / 100	3953 ms	100728 KiB

new_home

#include <bits/stdc++.h>
//#include <quadmath.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#define sz(x) (int)x.size()
//#define sqr(x) x*x
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("fast-math")
using namespace std;
//using namespace __gnu_pbds;

//#define int long long
//#define ld long double
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//typedef long long ll;

const int INF = 2e9;
const int MAX_ANS = 1e8;

int nn;

vector<int> t;

void build(int v, int tl, int tr, vector<int>& a)
{
    if (tl == tr)
    {
        t[v] = a[tl];
    }
    else
    {
        int tm = (tl + tr) >> 1;
        build(v * 2, tl, tm, a);
        build(v * 2 + 1, tm + 1, tr, a);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
}

void update(int v, int tl, int tr, int p, int x)
{
    if (tl == tr)
    {
        t[v] = x;
    }
    else
    {
        int tm = (tl + tr) >> 1;
        if (p <= tm)
            update(v * 2, tl, tm, p, x);
        else
            update(v * 2 + 1, tm + 1, tr, p, x);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
}

int get(int v, int tl, int tr, int l, int r)
{
    if (l > r || l < tl || tr < r)
        return -INF;
    if (tl == l && tr == r)
    {
        return t[v];
    }
    int tm = (tl + tr) >> 1;
    int ql = get(v * 2, tl, tm, l, min(r, tm));
    int qr = get(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
    return max(ql, qr);
}

//0 - add
//1 - query
//2 - rem
struct ev
{
    int x, type, ind, pos;
    ev() {}
    ev(int x, int type, int ind, int pos) : x(x), type(type), ind(ind), pos(pos) {}
    bool operator<(const ev& o)
    {
        if (x != o.x)
            return x < o.x;
        if (type != o.type)
            return type < o.type;
        return ind < o.ind;
    }
};

struct store
{
    int x, type, a, b;
    store() {}
    store(int x, int type, int a, int b) : x(x), type(type), a(a), b(b) {}
};

vector<set<pair<int, int> > > type_list;

vector<int> R;
vector<store> sts;
vector<int> compx;
vector<int> rev_compx;
vector<pair<int, int> > comp1;
vector<ev> evs;
vector<int> ans;
vector<pair<int, int> > qs;
vector<int> cnt;

int k;

int query(int b)
{
    int ind = upper_bound(rev_compx.begin(), rev_compx.end(), b) - rev_compx.begin() - 1;
    int cur = get(1, 0, nn - 1, 0, ind);
    if (cur == INF)
        return INF;
    return rev_compx[cur];
}

int query_easy(int b)
{
    int mx = 0;
    for (int i = 0; i < (int)R.size(); i++)
    {
        if (rev_compx[i] <= b)
        {
            mx = max(mx, R[i]);
        }
    }
    if (mx == INF)
        return INF;
    return rev_compx[mx];
}

void solve()
{
    int n, q;
    cin >> n >> k >> q;
    cnt.resize(k);
    type_list.resize(k);
    sts.resize(n);
    comp1.resize(n);
    compx.resize(n);
    rev_compx.resize(n + k);
    qs.resize(q);
    ans.resize(q);
    R.resize(n + k);
    nn = n + k;
    for (int i = 0; i < n; i++)
    {
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        t--;
        compx[i] = x;
        sts[i] = {x, t, a, b};
        evs.push_back({a, 0, i, x});
        evs.push_back({b, 2, i, x});
        comp1[i] = {x, i};
    }
    for (int i = 0; i < q; i++)
    {
        int t, x;
        cin >> x >> t;
        qs[i] = {x, t};
        evs.push_back({t, 1, i, x});
    }
    sort(evs.begin(), evs.end());
    sort(comp1.begin(), comp1.end());
    for (int i = 0; i < k; i++)
    {
        rev_compx[i] = -INF;
    }
    for (int i = 0; i < n; i++)
    {
        compx[comp1[i].second] = i + k;
        rev_compx[i + k] = comp1[i].first;
    }
    for (int i = 0; i < k; i++)
    {
        type_list[i].insert({i, i});
    }
    for (int i = 0; i < n + k; i++)
    {
        R[i] = -INF;
    }
    t.resize(4 * nn);
    build(1, 0, nn - 1, R);
    int cnt_zero = k;
    for (auto&[x, type, ind, pos] : evs)
    {
        if (type == 1)
        {
            //if (ind == 0)
            //cout << "hui";
            if (cnt_zero)
            {
                ans[ind] = -1;
            }
            else
            {
                int lt = 0, rt = MAX_ANS;
                while (rt - lt > 1)
                {
                    int mid = (lt + rt) >> 1;
                    int beg = pos - mid;
                    int ed = pos + mid;
                    int mx = query(beg);
                    if (mx < ed)
                    {
                        rt = mid;
                    }
                    else
                    {
                        lt = mid;
                    }
                }
                ans[ind] = lt;
            }
        }
        else
        {
            if (type == 0)
            {
                if (cnt[sts[ind].type] == 0) cnt_zero--;
                cnt[sts[ind].type]++;
                int t = sts[ind].type;
                auto it = type_list[t].lower_bound({compx[ind], -1});
                int rt = INF, lt = -INF;
                if (it != type_list[t].end()) rt = (*it).first;
                if (it != type_list[t].begin()) lt = (*(--it)).first;
                R[compx[ind]] = rt;
                update(1, 0, nn - 1, compx[ind], rt);
                type_list[t].insert({compx[ind], ind});
                if (lt != -INF)
                {
                    R[lt] = compx[ind];
                    update(1, 0, nn - 1, lt, compx[ind]);
                }
            }
            else
            {
                if (cnt[sts[ind].type] == 1) cnt_zero++;
                cnt[sts[ind].type]--;
                int t = sts[ind].type;
                auto it = type_list[t].upper_bound({compx[ind], ind});
                int rt = INF, lt = -INF;
                if (it != type_list[t].end()) rt = (*it).first;
                it = type_list[t].lower_bound({compx[ind], ind});
                if (it != type_list[t].begin()) lt = (*(--it)).first;
                if (lt != -INF)
                {
                    R[lt] = rt;
                    update(1, 0, nn - 1, lt, rt);
                }
                R[compx[ind]] = -INF;
                update(1, 0, nn - 1, compx[ind], -INF);
                type_list[t].erase({compx[ind], ind});
            }
        }
    }
    for (int i = 0; i < q; i++)
    {
        cout << ans[i] << endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/

/*
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
*/

/*
1 1 1
100000000 1 1 1
1 1
*/

/*
4 4
1 2 1 3
1 1
1 2
1 3
1 4
*/

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