Submission #689785

#	Time	Username	Problem	Language	Result	Execution time	Memory
689785		zeroesandones	Pilot (NOI19_pilot)	C++17	100 / 100	368 ms	52204 KiB

pilot

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

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;

#define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i)
#define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i)
#define nl "\n"
#define sp " "

#define all(x) (x).begin(), (x).end()
#define sc second
#define fr first
#define pb emplace_back

ll c2(ll x) {
    return (x * (x - 1)) / 2;
}

void solve()
{
    ll n, q;
    cin >> n >> q;

    ll a[n + 2] = {};
    FOR(i, 1, n + 1) {
        cin >> a[i];
    }

    stack<ll> st;
    st.push(0);
    a[0] = 1e15;

    ll l[n + 1], r[n + 1];
    FOR(i, 1, n + 1) {
        while(a[st.top()] < a[i])
            st.pop();
        l[i] = st.top();
        st.push(i);
    }

    while(!st.empty()) st.pop();
    st.push(n + 1);
    a[n + 1] = 1e15;
    FORD(i, n, 1) {
        while(a[st.top()] <= a[i])
            st.pop();
        r[i] = st.top();
        st.push(i);
    }

    ll total[(ll) 1e6 + 6] = {};
    FOR(i, 1, n + 1) {
        total[a[i]] += (i - l[i]) * (r[i] - i);
    }
    FOR(i, 1, ((ll) 1e6 + 6)) {
        total[i] += total[i - 1];
    }

    while(q--) {
        ll x;
        cin >> x;
        cout << total[x] << nl;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t = 1;
    // cin >> t;
    while (t--)
    {
        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: 11 / 11