Submission #285485

#TimeUsernameProblemLanguageResultExecution timeMemory
285485akobiMountains (NOI20_mountains)C++98
100 / 100
141 ms16524 KiB
#include <bits/stdc++.h> #define ll long long #define mp make_pair #define F first #define S second using namespace std; ll n,a[300005],id[300005],ans,f1[300005],f2[300005],x; pair<ll,ll> b[300005]; void upd1(ll u,ll x) { u++; while (u<=n) { f1[u]+=x; u+=(u&(-u)); } return; } ll get1(ll u) { u++; ll res=0; u--; while (u>0) { res+=f1[u]; u-=(u&(-u)); } return res; } void upd2(ll u,ll x) { u++; while (u<=n) { f2[u]+=x; u+=(u&(-u)); } return; } ll get2(ll u) { u++; ll res=0; u--; while (u>0) { res+=f2[u]; u-=(u&(-u)); } return res; } int main() { ios_base::sync_with_stdio(false); cin>>n; for (int i=0; i<n; i++) { cin>>a[i]; b[i]=mp(a[i],i); } sort(b,b+n); x=0; id[b[0].S]=x; for (int i=1; i<n; i++) { if (b[i].F>b[i-1].F) x++; id[b[i].S]=x; } for (int i=2; i<n; i++) upd2(id[i],1); upd1(id[0],1); for (int i=1; i<=n-2; i++) { ans+=get1(id[i])*get2(id[i]); upd1(id[i],1); upd2(id[i+1],-1); } cout<<ans<<endl; return 0; }
#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...