Submission #1123822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123822		ShadowShark	Pilot (NOI19_pilot)	C++20	100 / 100	597 ms	39004 KiB

pilot

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

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

bool cmp1(int x, int y) {return (a[x] != a[y] ? a[x] < a[y] : x < y);}
bool cmp2(int x, int y) {return (query[x] != query[y] ? query[x] < query[y] : x < y);}

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];
        num.push_back(i);
    }

    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (st.size() > 0 && a[st.top()] <= a[i]) st.pop();

        if (st.size() == 0) lt[i] = i - 1;
            else lt[i] = i - st.top() - 1;

        st.push(i);
    }

    while (st.size()) st.pop();
    for (int i = n; i >= 1; i--) {
        while (st.size() > 0 && a[st.top()] < a[i]) st.pop();

        if (st.size() == 0) rt[i] = n - i;
            else rt[i] = st.top() - i - 1;

        st.push(i);
    }

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

    sort(num.begin(), num.end(), cmp1);
    sort(event.begin(), event.end(), cmp2);

    int i = 0, j = 0;
    long long ans = 0;
    while (j < q) {
        while (i < n && a[num[i]] <= query[event[j]]) {
            int v = num[i];
            int x = lt[v], y = rt[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;
            i++;
        }
        res[event[j]] = ans; j++;
    }

    for (int i = 1; i <= q; i++)
        cout << res[i] << '\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: 11 / 11