oj.uz

Submission #199246

# Submission time Handle Problem Language Result Execution time Memory
199246 2020-01-30T15:33:05 Z wet_water New Home (APIO18_new_home) C++14
0 / 100
 2278 ms 94944 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

#define MAX_N 300005
#define f first
#define s second

using namespace std;

typedef pair<int, int> ii;
typedef pair<int, ii> pii;

class SegTree {
    private:
        ii tree[4 * MAX_N];
        multiset<int> c[4 * MAX_N];

    public:
        SegTree(int N) {

        }

        ii cmb(ii a, ii b) {
            if (a.f == -1)
                return (a);
            if (b.f == -1)
                return (b);

            return (ii(max(a.f, b.f), min(a.s, b.s)));
        }

        ii get_val(int l, int r, int a, int b, int ind) {
            if (a <= l && r <= b) { return (tree[ind]); }
            if (a > r || b < l) { return (ii(0, 1000000000)); }

            ii leftS = get_val(l, (l + r) / 2, a, b, 2 * ind);
            ii rightS = get_val((l + r) / 2 + 1, r, a, b, 2 * ind + 1);

            return (cmb(leftS, rightS));
        }

        ii query(int a, int b)
        { return (get_val(0, MAX_N, a, b, 1)); }

        void change_val(int l, int r, int newVal, int ind, int tmp) {
            if (tmp > r || tmp < l) { return; }
            if (l == r) {
                if (newVal > 0) {
                    c[ind].insert(newVal);
                    tree[ind].f = *c[ind].rbegin();
                    tree[ind].s = *c[ind].begin();
                } else {
                    if (c[ind].find(-newVal) != c[ind].end())
                        c[ind].erase(c[ind].find(-newVal));

                    if (c[ind].empty()) {
                        tree[ind].f = -1;
                        tree[ind].s = -1;
                    } else {
                        tree[ind].f = *c[ind].rbegin();
                        tree[ind].s = *c[ind].begin();
                    }
                }

                return;
            }

            change_val(l, (r + l) / 2, newVal, 2 * ind, tmp);
            change_val((r + l) / 2 + 1, r, newVal, 2 * ind + 1, tmp);

            tree[ind] = cmb(tree[2 * ind], tree[2 * ind + 1]);
        }

        void update(int ind, int val)
        { change_val(0, MAX_N, val, 1, ind); }
};

int ans[MAX_N];
int N, K, Q;

bool cmp(pii a, pii b) {
    return (abs(a.f) < abs(b.f));
}

int main() {
    cin >> N >> K >> Q;

    vector<pii> events;

    int a, b, c, d;
    for (int i = 0; i < N; i ++) {
        cin >> a >> b >> c >> d;
        events.push_back(pii(c, ii(a, b)));
        events.push_back(pii(-(d + 1), ii(a, b)));
    }

    sort(events.begin(), events.end(), cmp);

    SegTree seg(MAX_N);

    vector<pii> query (Q);
    for (int i = 0; i < Q; i ++) {
        cin >> query[i].s.f >> query[i].f;
        query[i].s.s = i;
    }

    sort(query.begin(), query.end());

    int lft = 0;
    for (int i = 0; i < Q; i ++) {
        while (abs(events[lft].f) <= query[i].f) {
            if (events[lft].f > 0) {
                seg.update(events[lft].s.s, events[lft].s.f);
            } else {
                seg.update(events[lft].s.s, -events[lft].s.f);
            }

            lft ++;
        }

        ii cur = seg.query(1, K);

        if (cur.f == -1) {
            ans[query[i].s.s] = -1;
        } else {
            ans[query[i].s.s] = max(abs(query[i].s.f - cur.f), abs(query[i].s.f - cur.s));
        }
    }

    for (int i = 0; i < Q; i ++)
        cout << ans[i] << endl;

    return (0);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 66040 KB Output is correct
2 Correct 43 ms 66044 KB Output is correct
3 Incorrect 43 ms 66040 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 66040 KB Output is correct
2 Correct 43 ms 66044 KB Output is correct
3 Incorrect 43 ms 66040 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1962 ms 94944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2278 ms 94628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 66040 KB Output is correct
2 Correct 43 ms 66044 KB Output is correct
3 Incorrect 43 ms 66040 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 66040 KB Output is correct
2 Correct 43 ms 66044 KB Output is correct
3 Incorrect 43 ms 66040 KB Output isn't correct
4 Halted 0 ms 0 KB -