Submission #876708

#TimeUsernameProblemLanguageResultExecution timeMemory
876708imarnMountains (NOI20_mountains)C++14
100 / 100
189 ms15868 KiB
#include<bits/stdc++.h> #define pb push_back #define ll long long #define f first #define s second #define sz(x) (int)x.size() #define pii pair<ll,ll> using namespace std; const int N=3e5+5; int fw[N]{0}; void add(int i){ for(;i<N;i+=i&-i)fw[i]++; } int qr(int i,int res=0){ for(;i;i-=i&-i)res+=fw[i]; return res; } int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); int n;cin>>n;vector<ll>b; ll a[n+1];for(int i=1;i<=n;i++)cin>>a[i],b.pb(a[i]); sort(b.begin(),b.end());b.erase(unique(b.begin(),b.end()),b.end()); ll tt[n+1]; for(int i=1;i<=n;i++){ int idx=lower_bound(b.begin(),b.end(),a[i])-b.begin(); tt[i] = qr(idx);add(idx+1); }ll ans=0; for(int i=1;i<=n;i++)fw[i]=0; for(int i=n;i>=1;i--){ int idx=lower_bound(b.begin(),b.end(),a[i])-b.begin(); tt[i] *= qr(idx);add(idx+1);ans+=tt[i]; }cout<<ans; }
#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...