Submission #728702

#	Time	Username	Problem	Language	Result	Execution time	Memory
728702		MilosMilutinovic	Mountains (NOI20_mountains)	C++14	100 / 100	183 ms	12476 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;

int n,fenv[300005],L[300005];
long long h[300005];

void compress()
{
    vector<long long> xs;
    for(int i=1;i<=n;i++) xs.push_back(h[i]);
    sort(xs.begin(),xs.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end());
    for(int i=1;i<=n;i++) h[i]=(int)(lower_bound(xs.begin(),xs.end(),h[i])-xs.begin())+1;
}

void update(int x)
{
    for(int i=x;i<=300000;i+=i&-i) fenv[i]+=1;
}
int query(int x)
{
    int res=0;
    for(int i=x;i>=1;i-=i&-i) res+=fenv[i];
    return res;
}

signed main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
    compress();
    for(int i=1;i<=n;i++) L[i]=query(h[i]-1),update(h[i]);
    for(int i=0;i<=300000;i++) fenv[i]=0;
    long long ans=0;
    for(int i=n;i>=1;i--) ans+=1ll*L[i]*query(h[i]-1),update(h[i]);
    printf("%lld",ans);
}

Compilation message (stderr)

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