Submission #645903

#	Time	Username	Problem	Language	Result	Execution time	Memory
645903		JJAnawat	Mountains (NOI20_mountains)	C++14	100 / 100	279 ms	27400 KiB

Mountains

#include<bits/stdc++.h>

using namespace std;

const int MXN=3e5+5;
long long n;
long long ar[MXN],pre[MXN],pos[MXN];
vector<long long> v;
unordered_map<long long,int> ump;
long long fw[2][MXN];

void upd(int o,int x){
    for(;x<MXN;x+=x&-x)
        fw[o][x]++;
}

long long qr(int o,int x){
    long long sum=0;
    for(;x>0;x-=x&-x)
        sum+=fw[o][x];
    return sum;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> ar[i];
        v.push_back(ar[i]);
    }
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end())-v.begin());
    for(int i=1;i<=v.size();i++){
        ump[v[i-1]]=i;
    }
    for(int i=1;i<=n;i++){
        ar[i]=ump[ar[i]];
        pre[i]=qr(0,ar[i]-1);
        upd(0,ar[i]);
    }
    for(int i=n;i>=1;i--){
        pos[i]=qr(1,ar[i]-1);
        upd(1,ar[i]);
    }

    long long ans=0;
    for(int i=1;i<=n;i++){
        ans+=(pre[i]*pos[i]);
    }
    cout << ans;
}

Compilation message (stderr)

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