Submission #720114

#	Time	Username	Problem	Language	Result	Execution time	Memory
720114		Cyanmond	Pilot (NOI19_pilot)	C++17	89 / 100	1086 ms	74692 KiB

pilot

#include <bits/stdc++.h>

using i64 = long long;

i64 c2(i64 x) {
    return x * (x + 1) / 2;
}

void solve() {
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> H(N), Y(Q);
    for (auto &e : H) std::cin >> e;
    for (auto &e : Y) std::cin >> e;
    std::vector<std::pair<int, int>> queries(Q);
    for (int i = 0; i < Q; ++i) queries[i] = {Y[i], i};
    std::sort(queries.begin(), queries.end());
    std::vector<std::pair<int, int>> mountains(N);
    for (int i = 0; i < N; ++i) mountains[i] = {H[i], i};
    std::sort(mountains.begin(), mountains.end());

    std::set<int> s;
    s.insert(-1);
    int j = 0;
    for (int i = 0; i < N; ++i) s.insert(--s.end(), i);
    s.insert(N);
    std::vector<i64> answer(Q);
    i64 countFlights = 0;
    for (int i = 0; i < N; ++i) {
        while (j != Q and queries[j].first < mountains[i].first) {
            answer[queries[j].second] = countFlights;
            ++j;
        }
        auto itr = s.lower_bound(mountains[i].second);
        const auto m = *itr;
        --itr;
        const auto l = *itr;
        ++itr;
        ++itr;
        const auto r = *itr;
        s.erase(--itr);
        countFlights -= c2(r - m - 1);
        countFlights -= c2(m - l - 1);
        countFlights += c2(r - l - 1);
    }
    while (j != Q) {
        answer[queries[j].second] = countFlights;
        ++j;
    }
    for (const auto e : answer) std::cout << e << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
}

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 0 / 11