Submission #538169

#	Time	Username	Problem	Language	Result	Execution time	Memory
538169		ToroTN	Mountains (NOI20_mountains)	C++14	100 / 100	651 ms	53332 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;
long long n,a[300005],kk=0,node,fen[300005],cnt,mount=0;
unordered_map<long long,long long> mp;
set<long long> s;
vector<long long> v[300005];
void up(long long u,long long val)
{
    while(u<=n)
    {
        fen[u]+=val;
        u+=(u&(-u));
    }
}
long long qq(long long u)
{
    cnt=0;
    while(u>0)
    {
        cnt+=fen[u];
        u-=(u&(-u));
    }
    return cnt;
}
long long query(long long l,long long r)
{
    return qq(r)-qq(l-1);
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        s.insert(a[i]);
    }
    for(auto it=s.begin();it!=s.end();it++)
    {
        if(mp[*it]==0)
        {
            ++kk;
            mp[*it]=kk;
        }
    }
    for(int i=1;i<=n;i++)
    {
        v[mp[a[i]]].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        //printf("%d\n",i);
        for(int j=0;j<v[i].size();j++)
        {
            node=v[i][j];
            //printf("%lld ",node);
            mount+=query(1,node-1)*query(node+1,n);
        }
        //printf("\n");
        for(int j=0;j<v[i].size();j++)
        {
            node=v[i][j];
            up(node,1);
        }
    }
    printf("%lld\n",mount);
}

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
Mountains.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
Mountains.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
Mountains.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         scanf("%lld",&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