Submission #219007

#	Time	Username	Problem	Language	Result	Execution time	Memory
219007		VEGAnn	New Home (APIO18_new_home)	C++14	100 / 100	2172 ms	82424 KiB

new_home

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define MP make_pair
#define PB push_back
#define pii pair<int,int>
#define ft first
#define sd second
#define sz(x) ((int)x.size())
using namespace std;
const int N = (1 << 19) + 10;
const int oo = int(2e9) + 7;
const int big = int(1e8);
vector<array<int, 4> > qr;
vector<pii> events[N];
vector<int> vc;
int a[N], b[N], x[N], t[N], n, k, q, ans[N], l[N], y[N];
int mrk[N], st[4 * N], nm[N];
map<pii, int> mp;
map<pii, int>::iterator ite, pre, net;

bool cmp(int x, int y){
    return l[x] < l[y];
}

void calc(){
    fill(mrk, mrk + n, 0);
    mp.clear();
    qr.clear();
    mp[MP(x[n], n)] = 0;

    for (int i = 0; i < k; i++){
        mp[MP(x[n + 1], n + 1)] = sz(qr);
        qr.PB({0, 0, sz(vc) - 1, 2 * big});

        for (pii ev : events[i]) {
            int nm = ev.sd, tim = ev.ft;

            if (mrk[nm] == 1){
                ite = mp.find(MP(x[nm], nm));
                net = next(ite);

                qr[ite -> sd][2] = qr[net -> sd][2] = tim;

                mp.erase(ite);
                pre = prev(net);

                net -> sd = sz(qr);

                int i2 = net -> ft.sd;
                int i1 = pre -> ft.sd;
                int len = (x[i2] - x[i1]) / 2;

                qr.PB({x[i2] - len, tim, sz(vc) - 1, len});
            } else {
                mp[MP(x[nm], nm)] = 0;

                ite = mp.find(MP(x[nm], nm));
                pre = prev(ite);
                net = next(ite);

                qr[net -> sd][2] = tim;

                int i1 = pre -> ft.sd;
                int i2 = ite -> ft.sd;
                int i3 = net -> ft.sd;

                net -> sd = sz(qr);
                int len = (x[i3] - x[i2]) / 2;
                qr.PB({x[i3] - len, tim, sz(vc) - 1, len});

                ite -> sd = sz(qr);
                len = (x[i2] - x[i1]) / 2;
                qr.PB({x[i2] - len, tim, sz(vc) - 1, len});
            }

            mrk[nm]++;
        }
    }

    sort(all(qr));

    int siz = 1;

    while (siz < sz(vc)) siz <<= 1;

    fill(st, st + 2 * siz, 0);

    sort(nm, nm + q, cmp);

    int i1 = 0, i2 = 0;

    for (; i1 < q; i1++){
        int i = nm[i1];

        while (i2 < sz(qr) && qr[i2][0] <= l[i]){
            int lf = qr[i2][1] + siz, rt = qr[i2][2] + siz - 1;
            int vl = qr[i2][0] + qr[i2][3];

            while (lf <= rt){
                if (lf & 1)
                    st[lf] = max(st[lf], vl);

                if (!(rt & 1))
                    st[rt] = max(st[rt], vl);

                lf = (lf + 1) >> 1;
                rt = (rt - 1) >> 1;
            }

            i2++;
        }

        int loc = siz + y[i];

        for (; loc > 0; loc >>= 1)
            ans[i] = max(ans[i], st[loc] - l[i]);
    }
}

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

//    freopen("in.txt","r",stdin);

    cin >> n >> k >> q;

    for (int i = 0; i < n; i++){
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        t[i]--; b[i]++;
        vc.PB(a[i]);
        vc.PB(b[i]);
    }

    vc.PB(0);
    vc.PB(big + 1);
    sort(all(vc));
    vc.resize(unique(all(vc)) - vc.begin());

    for (int i = 0; i < n; i++){
        a[i] = lower_bound(all(vc), a[i]) - vc.begin();
        b[i] = lower_bound(all(vc), b[i]) - vc.begin();

        events[t[i]].PB(MP(a[i], i));
        events[t[i]].PB(MP(b[i], i));
    }

    for (int i = 0; i < k; i++){
        if (!sz(events[i])) {
            for (; q; q--) cout << "-1\n";
            return 0;
        }

        sort(all(events[i]));
    }

    for (int i = 0; i < q; i++){
        cin >> l[i] >> y[i];
        y[i] = upper_bound(all(vc), y[i]) - vc.begin() - 1;
        nm[i] = i;
    }

    x[n] = -2 * big;
    x[n + 1] = +2 * big;

    calc();

    for (int i = 0; i < q; i++)
        l[i] = big - l[i];

    for (int i = 0; i < n; i++)
        x[i] = big - x[i];

    calc();

    for (int i = 0; i < q; i++)
        cout << (ans[i] >= big ? -1 : ans[i]) << '\n';

    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