Submission #1088283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088283		whtth	Mountains (NOI20_mountains)	C++14	100 / 100	419 ms	41820 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;
long long n, h[300010], ans=0, bit[2][300010], f[300010], cnt=0;\
unordered_map<long long, int> g;
void add(long long i, long long v, long long id){
    while(i<=cnt){
        bit[id][i]+=v;
        i+=i&-i;
    }
}
long long sum(long long i, long long id){
    long long s=0;
    while(i>0){
        s+=bit[id][i];
        i-=i&-i;
    }
    return s;
}
set<long long> thutu;
int main(){
    //freopen("mountains.inp", "r", stdin);
    //freopen("mountains.out", "w", stdout);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i], thutu.insert(h[i]);
    for(auto x : thutu){
        cnt++;
        f[cnt]=x;
        g[x]=cnt;
    }
    add(g[h[1]], 1, 0);
    for(int i=3;i<=n;i++){
        add(g[h[i]], 1, 1);
    }
    for(int i=2;i<n;i++){
        ans+=(sum(g[h[i]]-1, 0)*sum(g[h[i]]-1, 1));
        add(g[h[i]], 1, 0);
        add(g[h[i+1]], -1, 1);
    }
    cout<<ans;
    return 0;
}

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