Submission #227170

#TimeUsernameProblemLanguageResultExecution timeMemory
227170TheKingAleksMountains (NOI20_mountains)C++14
86 / 100
614 ms93932 KiB
#include<bits/stdc++.h> #define ll long long #define endl '\n' using namespace std; const ll MAX_N = 3e5+2; ll a[MAX_N]; ll res; set<ll> s; unordered_map<ll,ll> m; ll br=1; vector<ll> tree1(MAX_N*2); vector<ll> tree2(MAX_N*2); void update(vector<ll> &tree,ll node,ll tl,ll tr,ll l,ll r) { if(tl > r || tr < l)return; if(tl == tr) { tree[node]++; return; } ll mid = (tl+tr)/2; update(tree,node*2,tl,mid,l,r); update(tree,node*2+1,mid+1,tr,l,r); tree[node] = tree[node*2]+tree[node*2+1]; } ll query(vector<ll> &tree,ll node,ll tl,ll tr,ll l,ll r) { if(tl > r || tr < l)return 0; if(tl >= l && tr <= r) { return tree[node]; } ll mid = (tl+tr)/2; return query(tree,node*2,tl,mid,l,r)+query(tree,node*2+1,mid+1,tr,l,r); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll n; cin>>n; vector<ll> l(n); vector<ll> r(n); for(ll i=0; i<n; i++) { cin>>a[i]; s.insert(a[i]); } for(auto &it : s) { m[it] = br; br++; } br--; update(tree1,1,1,br,m[a[0]],m[a[0]]); for(ll i=1; i<n; i++) { l[i] = query(tree1,1,1,br,1,m[a[i]]-1); update(tree1,1,1,br,m[a[i]],m[a[i]]); } update(tree2,1,1,br,m[a[n-1]],m[a[n-1]]); for(ll i=n-2; i>=0; i--) { r[i] = query(tree2,1,1,br,1,m[a[i]]-1); update(tree2,1,1,br,m[a[i]],m[a[i]]); } for(ll i=0;i<n;i++) { res+=(l[i]*r[i]); } cout<<res<<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...