Submission #642806

#TimeUsernameProblemLanguageResultExecution timeMemory
642806CodulaMountains (NOI20_mountains)C++17
100 / 100
901 ms88296 KiB
//IOI 2023 I am coming. #include "bits/stdc++.h" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fast ios_base::sync_with_stdio(false);cin.tie(nullptr) #define int int64_t #define pb push_back #define deb(x) cerr<<"("<<#x<<"="<<x<<','<<__LINE__<<")"<<endl; #define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> int32_t main(){ fast; int n; cin>>n; vector<int>a(n); for(int i=0;i<n;++i){ cin>>a[i]; } ordered_set o1,o2; //~ map<int,int>mp; vector<int>pref(3e5+1),pref2(3e5+1); map<int,int>mp,mp2; for(int i=0;i<n;++i){ int dx=o1.order_of_key({a[i],i})-mp[a[i]]; pref[i]=dx; o1.insert({a[i],i}); mp[a[i]]+=1; } //~ map<int,int>mp2; for(int i=n-1;i>=0;--i){ int dx=o2.order_of_key({a[i],-i})-mp2[a[i]]; pref2[i]=dx; o2.insert({a[i],-i}); mp2[a[i]]+=1; } int ans=0; for(int i=0;i<n;++i){ //~ deb(pref[i]); //~ deb(pref2[i]); ans+=(pref[i]*pref2[i]); } cout<<ans<<"\n"; 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...