Submission #570216

#TimeUsernameProblemLanguageResultExecution timeMemory
570216thatsgonzalezMountains (NOI20_mountains)C++14
100 / 100
125 ms12116 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vl; typedef pair <ll,ll> pl; typedef vector<pl> vpl; #define s second #define f first int n; struct FT { int n; vl dp; FT (int n){ this->n = n; dp.assign(n+1,0); } int lsb(int x){ return x & (-x); } ll query(int ind){ ll res=0; while(ind){ res+=dp[ind]; ind-=lsb(ind); } return res; } void add(int ind, ll value){ while(ind<=n){ dp[ind]+=value; ind+=lsb(ind); } } }; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; FT ft1(n),ft2(n); ll a[n]; vpl aux(n); for(int i=0; i<n; i++){ ll x; cin>>x; aux[i]={x,i}; } sort(aux.begin(),aux.end()); a[aux[0].s]=1; int temp=1; for(int i=1; i<n; i++){ if(aux[i].f==aux[i-1].f) a[aux[i].s]=temp; else temp++, a[aux[i].s]=temp; } //for(auto &x: a) cout<<x<<" "; cout<<endl; ll mx=0; for(int i=n-1; i>=0; i--){ mx=max(mx,a[i]); ft1.add(a[i],1); } //cout<<query(mx-1,1)<<endl; //int top=n+99; ll ans=0; for(int i=0; i<n; i++){ ft1.add(a[i],-1LL); //cout<<query(a[i]-1,0)<<" "<<query(a[i]-1,1)<<endl; ans+=(ll)(ft1.query(a[i]-1)*(ft2.query(a[i]-1))); ft2.add(a[i],1LL); } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...