Submission #331390

#	Time	Username	Problem	Language	Result	Execution time	Memory
331390		Sho10	Mountains (NOI20_mountains)	C++14	100 / 100	537 ms	36572 KiB

Mountains

#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#define ll long long
#define double long double
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000007
#define PI 3.14159265359
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005ll
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n,pref[300005],suf[300005],a[300005],bit[300005];
vector<ll>v;
map<ll,ll>m;
void update(ll pos,ll val){
for(;pos<=n;pos+=pos&(-pos)){
    bit[pos]+=val;
}
}
ll query(ll pos){
ll res=0;
for(;pos;pos-=pos&(-pos)){
    res+=bit[pos];
}
return res;
}
int32_t main(){
CODE_START
cin>>n;
for(ll i=1;i<=n;i++)
{
    cin>>a[i];
    v.pb(a[i]);
}
sort(v.begin(),v.end());
ll s1=1;
for(ll i=0;i<v.size();i++)
if(i==0){
    m[v[i]]=s1++;
}else if(v[i]==v[i-1]){
continue;
}else {
m[v[i]]=s1++;
}
for(ll i=1;i<=n;i++)
{
a[i]=m[a[i]];
}
for(ll i=1;i<=n;i++){
    pref[i]=query(a[i]-1);
    update(a[i],1ll);
}
memset(bit,0,sizeof(bit));
for(ll i=n;i>=1;i--)
{
    suf[i]=query(a[i]-1);
    update(a[i],1ll);
}
ll ans=0;
for(ll i=1;i<=n;i++)
{
    ans+=pref[i]*suf[i];
}
rc(ans);
}

Compilation message (stderr)

Mountains.cpp: In function 'int32_t main()':
Mountains.cpp:46:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 | for(ll i=0;i<v.size();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