Submission #1026986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026986		ricardsjansons	Pilot (NOI19_pilot)	C++17	89 / 100	1028 ms	43688 KiB

pilot

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;

    vector<pair<int, int>> h(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> h[i].first;
        h[i].second = i;
    }
    sort(h.begin(), h.end());
    h.push_back({1e6 + 1, n + 1});

    vector<pair<int, int>> y(q);
    for (int i = 0; i < q; i++) {
        cin >> y[i].first;
        y[i].second = i;
    }
    sort(y.begin(), y.end());

    vector<long long> l(n + 2);
    vector<long long> r(n + 2);
    vector<long long> res(q, -1);
    long long flights = 0;
    int j = 0;
    for (int i = 1; i <= n; i++) {
        while (j < q && h[i].first > y[j].first) {
            res[y[j].second] = flights;
            j++;
        }

        int index = h[i].second;

        l[index] = l[index - 1] + 1;
        r[index] = r[index + 1] + 1;

        if (r[index] > 1) {
            l[index + r[index] - 1] += l[index];
        }
        if (l[index] > 1) {
            r[index - l[index] + 1] += r[index];
        }

        flights += l[index] * r[index];
    }

    for (long long v : res) {
        cout << (v >= 0 ? v : flights) << endl;
    }
}

• 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