Submission #227169

#TimeUsernameProblemLanguageResultExecution timeMemory
227169TheKingAleksMountains (NOI20_mountains)C++14
2 / 100
52 ms9208 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const int MAX_N = 3e5+2; int a[MAX_N]; int res; set<int> s; unordered_map<int,int> m; int br=1; vector<int> tree1(MAX_N*2); vector<int> tree2(MAX_N*2); void update(vector<int> &tree,int node,int tl,int tr,int l,int r) { if(tl > r || tr < l)return; if(tl == tr) { tree[node]++; return; } int 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]; } int query(vector<int> &tree,int node,int tl,int tr,int l,int r) { if(tl > r || tr < l)return 0; if(tl >= l && tr <= r) { return tree[node]; } int 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); int n; cin>>n; vector<int> l(n); vector<int> r(n); for(int 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(int 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(int 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(int 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...