Submission #393594

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
393594	2021-04-24T05:13:01 Z	KoD	New Home (APIO18_new_home)	C++17	10 / 100	1358 ms	86092 KB

new_home

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

using ll = long long;

constexpr ll INF = 1000000000;
constexpr ll MAX = 200000000;

struct Event {
    Vec<int> query;
    Vec<int> remove;
    Event(): query(), remove() { }
};

int main() {
    int N, K, Q;
    std::cin >> N >> K >> Q;
    Vec<ll> X(N), A(N), B(N);
    Vec<int> T(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> X[i] >> T[i] >> A[i] >> B[i];
        assert(A[i] == 1);
        X[i] *= 2;
        T[i] -= 1;
    }
    Vec<ll> L(Q), Y(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> L[i] >> Y[i];
        L[i] *= 2;
    }
    Vec<std::multiset<ll>> store(K);
    std::map<ll, ll> map;
    for (int i = 0; i < N; ++i) {
        store[T[i]].insert(X[i]);
    }
    const auto add = [&](const ll x, const ll y) {
        if (map.empty()) {
            map.emplace(x, y);
            return;
        }
        while (map.begin() -> first <= x) {
            auto itr = std::prev(map.upper_bound(x));
            if (itr -> second - (x - itr -> first) >= y) {
                return;
            }
            if (y - (x - itr -> first) >= itr -> second) {
                map.erase(itr);
            }
            else {
                break;
            }
        }
        while (map.rbegin() -> first >= x) {
            auto itr = map.lower_bound(x);
            if (itr -> second - (itr -> first - x) >= y) {
                return;
            }
            if (y - (itr -> first - x) >= itr -> second) {
                map.erase(itr);
            }
            else {
                break;
            }
        }
        map.emplace(x, y);
    };
    const auto get = [&](const ll x) {
        ll ret = 0;
        {
            auto itr = std::prev(map.upper_bound(x));
            ret = std::max(ret, itr -> second - (x - itr -> first));
        }
        {
            auto itr = map.lower_bound(x);
            ret = std::max(ret, itr -> second - (itr -> first - x));
        }
        return ret;
    };
    for (int i = 0; i < K; ++i) {
        store[i].insert(-INF);
        store[i].insert(INF);
        auto itr = store[i].begin();
        while (std::next(itr) != store[i].end()) {
            const auto mid = (*std::next(itr) + *itr) / 2;
            const auto len = (*std::next(itr) - *itr) / 2;
            add(mid, len);
            ++itr;
        }
    }
    for (int i = 0; i < Q; ++i) {
        const auto ans = get(L[i]);
        if (ans == MAX) {
            std::cout << -1 << '\n';
        }
        else {
            std::cout << ans / 2 << '\n';
        }
    }
    // std::map<ll, Event> map;
    // for (int i = 0; i < N; ++i) {

    // }   
    return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Runtime error	1 ms	332 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Runtime error	1 ms	332 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	819 ms	38652 KB	Output is correct
2	Correct	1022 ms	33108 KB	Output is correct
3	Correct	973 ms	86092 KB	Output is correct
4	Correct	841 ms	57652 KB	Output is correct
5	Correct	1358 ms	59564 KB	Output is correct
6	Correct	1032 ms	44980 KB	Output is correct
7	Correct	754 ms	86072 KB	Output is correct
8	Correct	749 ms	57776 KB	Output is correct
9	Correct	737 ms	47824 KB	Output is correct
10	Correct	776 ms	42424 KB	Output is correct
11	Correct	771 ms	42004 KB	Output is correct
12	Correct	743 ms	42336 KB	Output is correct