oj.uz

답안 #393602

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
393602 2021-04-24T05:21:19 Z KoD 새 집 (APIO18_new_home) C++17
33 / 100
 3293 ms 162552 KB 
#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) {
        while (!map.empty() and 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.empty() and 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;
        }
    } 
    Vec<ll> ans(Q);
    std::map<ll, Event> events;
    for (int i = 0; i < N; ++i) {
        events[B[i]].remove.push_back(i);
    }   
    for (int i = 0; i < Q; ++i) {
        events[Y[i]].query.push_back(i);
    }
    for (const auto& [time, event]: events) {
        for (const auto i: event.query) {
            ans[i] = get(L[i]);
        }
        for (const auto i: event.remove) {
            const auto t = T[i];
            const auto x = X[i];
            auto itr = store[t].find(x);
            assert(itr != store[t].end());
            add((*std::next(itr) + *std::prev(itr)) / 2, (*std::next(itr) - *std::prev(itr)) / 2);
            store[t].erase(itr);
        }
    }
    for (const auto x: ans) {
        if (x >= MAX) {
            std::cout << -1 << '\n';
        }
        else {
            std::cout << x / 2 << '\n';
        }
    }
    return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 1 ms 424 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 1 ms 424 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1317 ms 80020 KB Output is correct
2 Correct 1623 ms 72464 KB Output is correct
3 Correct 1271 ms 113720 KB Output is correct
4 Correct 1242 ms 85484 KB Output is correct
5 Correct 2669 ms 88496 KB Output is correct
6 Correct 1764 ms 73868 KB Output is correct
7 Correct 1151 ms 113652 KB Output is correct
8 Correct 1115 ms 85564 KB Output is correct
9 Correct 1088 ms 75676 KB Output is correct
10 Correct 1197 ms 70928 KB Output is correct
11 Correct 937 ms 70508 KB Output is correct
12 Correct 936 ms 70744 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1918 ms 108260 KB Output is correct
2 Correct 631 ms 37188 KB Output is correct
3 Correct 2356 ms 120236 KB Output is correct
4 Correct 1837 ms 161424 KB Output is correct
5 Correct 1922 ms 127244 KB Output is correct
6 Correct 1865 ms 132972 KB Output is correct
7 Correct 3293 ms 136748 KB Output is correct
8 Correct 2613 ms 122184 KB Output is correct
9 Correct 1707 ms 162552 KB Output is correct
10 Correct 1734 ms 130876 KB Output is correct
11 Correct 1794 ms 122328 KB Output is correct
12 Correct 2033 ms 119576 KB Output is correct
13 Correct 1131 ms 117308 KB Output is correct
14 Correct 1128 ms 117852 KB Output is correct
15 Correct 1214 ms 117624 KB Output is correct
16 Correct 1301 ms 119044 KB Output is correct
17 Correct 1315 ms 117936 KB Output is correct

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 1 ms 424 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 1 ms 424 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -