Submission #1190734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190734		aladdin1	Mountains (NOI20_mountains)	C++20	100 / 100	481 ms	19212 KiB

Mountains

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
#define all(v) v.begin(),v.end()
#define INF 1000000000
using namespace std;
const int MAX=2e5+5;
const int N=3e5+5;
const int MOD = 1e9 + 7;
/*
----------------------------------------------------------------------------------
                                                                                  |
   BBBBBBBBBB   LL        BBBBBBBBBB  DDDDDDDD     DDDDDDD     III   N      N     |
   BB      BB   LL        BB      BB  DD     DD    DD     DD   III   NN     N     |
   BB      BB   LL        BB      BB  DD     DD    DD     DD   III   N N    N     |
   BBBBBBBBBB   LL        BBBBBBBBBB  DD     DD    DD     DD   III   N  N   N     |
   BB      BB   LL        BB      BB  DD     DD    DD     DD   III   N   N  N     |
   BB      BB   LL        BB      BB  DD     DD    DD     DD   III   N    N N     |
   BB      BB   LL        BB      BB  DD     DD    DD     DD   III   N     NN     |
   BB      BB   LLLLLLLL  BB      BB  DDDDDDDD     DDDDDDD     III   N      N     |
                                                                                  |
----------------------------------------------------------------------------------

*/
vector<int>t;
void update(int v,int l,int r,int pos,int val){
    if(l==r){
        t[v]+=val;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid) update(2*v,l,mid,pos,val);
    else update(2*v+1,mid+1,r,pos,val);
    t[v]=t[2*v]+t[2*v+1];
}
int query(int v,int l,int r,int tl,int tr){
    if(tl>r || tr<l) return 0;
    if(tl<=l && r<=tr) return t[v];
    int mid=(l+r)/2;
    return query(2*v,l,mid,tl,tr)+query(2*v+1,mid+1,r,tl,tr);
}
void solve(){
    int n;cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;i++)cin>>v[i];
    vector<int>comp = v;
    sort(comp.begin(),comp.end());
    comp.erase(unique(comp.begin(),comp.end()),comp.end());
    int m=comp.size();
    t.assign(4*m,0);
    vector<int>L(n,0),R(n,0);
    for(int i=0;i<n;i++){
        int pos=lower_bound(comp.begin(), comp.end(),v[i])-comp.begin()+1;
        L[i] = query(1,1,m,1,pos - 1);
        update(1,1,m,pos,1);
    }
    t.assign(4*m,0);
    for(int i=n-1;i>=0;--i){
        int pos=lower_bound(comp.begin(), comp.end(),v[i])-comp.begin()+1;
        R[i] = query(1,1,m,1,pos - 1);
        update(1,1,m,pos,1);
    }
    int ans=0;
    for(int i=0;i<n;i++){
        ans+=L[i]*R[i];
    }
    cout<<ans<<endl;
}
signed main(){
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
}

• 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