Submission #1123806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123806		ShadowShark	Pilot (NOI19_pilot)	C++17	89 / 100	1101 ms	134624 KiB

pilot

#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e6 + 5;
int n, a[maxN], query[maxN], RMQ[21][maxN];
long long res[maxN];
vector<int> event[maxN];

int getMax(int l, int r) {
    int bit = 31 - __builtin_clz(r - l + 1);
    return max(RMQ[bit][l], RMQ[bit][r - (1 << bit) + 1]);
}

int find_left(int pos) {
    int low = 1, high = pos - 1, ans = pos;

    while (low <= high) {
        int mid = (low + high) >> 1;

        if (getMax(mid, pos) == a[pos]) {
            ans = mid;
            high = mid - 1;
        }
        else low = mid + 1;
    }

    return pos - ans;
}

int find_right(int pos) {
    int low = pos + 1, high = n, ans = pos;

    while (low <= high) {
        int mid = (low + high) >> 1;

        if (getMax(pos + 1, mid) < a[pos]) {
            ans = mid;
            low = mid + 1;
        }
        else high = mid - 1;
    }

    return ans - pos;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        RMQ[0][i] = a[i];
        event[a[i]].push_back(i);
    }

    for (int k = 1; k <= 19; k++)
        for (int i = 1; i + (1 << k) - 1 <= n; i++)
            RMQ[k][i] = max(RMQ[k - 1][i], RMQ[k - 1][i + (1 << (k - 1))]);

    for (int i = 1; i <= q; i++) {
        cin >> query[i];
        event[query[i]].push_back(-i);
    }

    long long ans = 0;
    for (int val = 1; val <= 1000000; val++) {
        for (auto v: event[val]) {
            //cout << "Event " << v << '\n';
            if (v > 0) {
                int x = find_left(v), y = find_right(v);
                ans = ans - 1LL * x * (x + 1) / 2;
                ans = ans - 1LL * y * (y + 1) / 2;
                ans = ans + 1LL * (x + y + 1) * (x + y + 2) / 2;
                //cout << x << ' ' << y <<  ' ' << ans << '\n';
            }
            else {
                res[-v] = ans;
                //cout << ans << '\n';
            }
        }
    }

    for (int i = 1; i <= q; i++)
        cout << res[i] << ' ';
    cout << '\n';
}

• 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