Submission #402894

#	Time	Username	Problem	Language	Result	Execution time	Memory
402894		Fidisk	Mountains (NOI20_mountains)	C++14	100 / 100	630 ms	29600 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;
 
#define oo 1e15
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) ((xxxx>>(aaaa-1))&1)
#define int long long
 
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;
 
const ll base=361;
const ll mod=998244353;
const ld eps=1e-5;
const ll maxn=1e6;
 
struct segtree_ele{
    int val,l,r;
} segtree[10000009];
 
ll res;
int sizet,l[400009],a[400009],n,i,cnt;
vector<pll> g;
 
int getnode(int &x) {
    if (x==0) {
        sizet++;
        x=sizet;
        segtree[x]={0,0,0};
    }
    return x;
}
 
void update(int id,int l,int r,int u) {
    if (l>r||r<u||l>u) {
        return;
    }
    if (l==u&&r==u) {
        segtree[id].val++;
        return;
    }
    int mid=(r+l)/2;
    if (mid<u) {
        update(getnode(segtree[id].r),mid+1,r,u);
    }
    else {
        update(getnode(segtree[id].l),l,mid,u);
    }
    segtree[id].val=segtree[getnode(segtree[id].l)].val+segtree[getnode(segtree[id].r)].val;
}
 
int get(int id,int l,int r,int u,int v) {
    if (l>r||r<u||l>v) {
        return 0;
    }
    if (u<=l&&r<=v) {
        return segtree[id].val;
    }
    int mid=(r+l)/2;
    return get(getnode(segtree[id].l),l,mid,u,v)+get(getnode(segtree[id].r),mid+1,r,u,v);
}
 
int32_t main(){
    IO;
    cin>>n;
    g.push_back({-1,0});
    for (i=1;i<=n;i++) {
        cin>>a[i];
        g.push_back({a[i],i});
    }
    sort(g.begin(),g.end());
    for (i=1;i<=n;i++) {
        if (g[i].fi!=g[i-1].fi) {
            cnt++;
        }
        a[g[i].se]=cnt;
    }
    sizet=0;
    getnode(a[0]);
    for (i=1;i<=n;i++) {
        //cout<<a[i]<<' ';
        l[i]=get(1,1,maxn,1,a[i]-1);
        update(1,1,maxn,a[i]);
    }
    //cout<<'\n';
    sizet=0;
    a[0]=0;
    getnode(a[0]);
    for (i=n;i>=1;i--) {
        //cout<<l[i]<<' '<<get(1,1,maxn,1,a[i]-1)<<'\n';
        res+=ll(l[i])*ll(get(1,1,maxn,1,a[i]-1));
        update(1,1,maxn,a[i]);
    }
    cout<<res<<'\n';
}

• 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