Submission #1191303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191303		kamal1122333	Mountains (NOI20_mountains)	C++20	64 / 100	2095 ms	12100 KiB

Mountains

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
using namespace std;


const ll INF=1e18+9;

vector<ll> st, v;

void build(ll l, ll r, ll ind){
    if (l==r){
        st[ind]=v[l];
        return;
    }
    ll mid=(l+r)/2;
    build(l, mid, ind*2);
    build(mid+1, r, ind*2+1);
    st[ind]=max(st[ind*2], st[ind*2+1]);
}
ll say;
void getans(ll l, ll r, ll ind, ll ql, ll qr, ll x){
    if (ql>r or qr<l) return;
    if (x>st[ind] and l>=ql and r<=qr){
        say+=r-l+1;
        return;
    }
    if (l==r) return;
    ll mid=(l+r)/2;
    getans(l, mid, ind*2, ql, qr, x);
    getans(mid+1, r, ind*2+1, ql, qr, x);
}

void solve(){
    ll n;
    cin>>n;
    v.resize(n+1);
    st.resize(4*n+1, 0);
    for (int i=1; i<=n; i++){
        cin>>v[i];
    }
    build(1, n, 1);
    ll ans=0;
    for (int i=2; i<=n-1; i++){
        ll cem=1;
        say=0;
        getans(1, n, 1, 1, i-1, v[i]);
        cem*=say;
        say=0;
        getans(1, n, 1, i+1, n, v[i]);
        cem*=say;
        ans+=cem;
    }
    cout<<ans<<endl;
}

int main()
{
    ll t=1;
    // cin>>t;
    while (t--){
        solve();
    }

    return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 9
• Subtask 4: 36 / 36
• Subtask 5: 28 / 28
• Subtask 6: 0 / 9
• Subtask 7: 0 / 12