Submission #586498

#	Time	Username	Problem	Language	Result	Execution time	Memory
586498		krit3379	Mountains (NOI20_mountains)	C++17	100 / 100	783 ms	34076 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 300005

long long a[N],fen[N],l[N],r[N],ans;
map<long long,int> mp;

void upd(int x){
    while(x<N){
        fen[x]++;
        x+=x&-x;
    }
}

long long sol(int x){
    long long ans=0;
    while(x){
        ans+=fen[x];
        x-=x&-x;
    }
    return ans;
}

int main(){
    int n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%lld",&a[i]),mp[a[i]];
    i=0;
    for(auto &[x,y]:mp)y=++i;
    for(i=1;i<=n;i++){
        l[i]=sol(mp[a[i]]);
        upd(mp[a[i]]+1);
    }
    for(i=1;i<=n;i++)fen[i]=0;
    for(i=n;i;i--){
        r[i]=sol(mp[a[i]]);
        upd(mp[a[i]]+1);
    }
    for(i=1;i<=n;i++)ans+=l[i]*r[i];
    printf("%lld",ans);
    return 0;
}

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Mountains.cpp:29:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     for(i=1;i<=n;i++)scanf("%lld",&a[i]),mp[a[i]];
      |                      ~~~~~^~~~~~~~~~~~~~

• 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