oj.uz

Submission #219003

# Submission time Handle Problem Language Result Execution time Memory
219003 2020-04-03T11:13:05 Z VEGAnn New Home (APIO18_new_home) C++14
10 / 100
 1474 ms 75452 KB 
#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 = 300100;
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] + 1) / 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Incorrect 9 ms 7552 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Incorrect 9 ms 7552 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 46012 KB Output is correct
2 Correct 987 ms 58340 KB Output is correct
3 Correct 892 ms 75452 KB Output is correct
4 Correct 780 ms 60192 KB Output is correct
5 Correct 1474 ms 71620 KB Output is correct
6 Correct 1026 ms 59204 KB Output is correct
7 Correct 729 ms 75324 KB Output is correct
8 Correct 704 ms 59320 KB Output is correct
9 Correct 734 ms 58056 KB Output is correct
10 Correct 840 ms 55692 KB Output is correct
11 Correct 769 ms 57664 KB Output is correct
12 Correct 736 ms 55896 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1118 ms 48064 KB Output is correct
2 Incorrect 915 ms 49752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Incorrect 9 ms 7552 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Incorrect 9 ms 7552 KB Output isn't correct
6 Halted 0 ms 0 KB -