제출 #1224762

#제출 시각아이디문제언어결과실행 시간메모리
1224762chinhhoangMountains (NOI20_mountains)C++20
100 / 100
107 ms21704 KiB
#include <bits/stdc++.h> using namespace std; int FT[3000002]; void updateFT(int i,int val){ while(i<300000){ FT[i]+=val; i+=i&-i; } } int getFT(int i){ int s=0; while(i>0){ s+=FT[i]; i-=i&-i; } return s; } int main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n; cin>>n; vector<long long>a(n+1,0),val,pre(n+1,0),suf(n+1,0); for(int i=1;i<=n;i++)cin>>a[i],val.push_back(a[i]); sort(val.begin(),val.end()); val.erase(unique(val.begin(),val.end()),val.end()); for(int i=1;i<=n;i++)a[i]=int(lower_bound(val.begin(),val.end(),a[i])-val.begin())+1; for(int i=1;i<=n;i++)pre[i]=getFT(a[i]-1),updateFT(a[i],1); memset(FT,0,sizeof(FT)); for(int i=n;i>=1;i--)suf[i]=getFT(a[i]-1),updateFT(a[i],1); long long ans=0; for(int i=1;i<=n;i++)ans+=pre[i]*suf[i]; cout<<ans; 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...