Submission #1093348

#TimeUsernameProblemLanguageResultExecution timeMemory
1093348asli_bgUntitled (POI11_rot)C++11
63 / 100
86 ms27732 KiB
#pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> inset; #define int long long #define fi first #define se second #define all(x) x.begin(),x.end() #define pb push_back #define FOR(i,a) for(int i=0;i<(a);i++) #define FORE(i,a,b) for(int i=(a);i<(b);i++) #define cont(x) {for(auto el:x) cout<<el<<' ';cout<<endl;} #define contp(x) {for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;} #define sp <<" "<< #define mid (l+r)/2 #define endl '\n' #define DEBUG(X) {cout<<#X<<' '<<(X)<<endl;} #define carp(x,y) ((x%MOD)*(y%MOD))%MOD #define topla(x,y) ((x%MOD)+(y%MOD))%MOD typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vii; typedef vector<bool> vb; const int MAXN=2e5+5; const int INF=1e9+7; const int MOD=1e9+7; int n; int t[MAXN]; int adj[MAXN][2]; int cur; bool leaf[MAXN]; void oku(int nd){ int el; cin>>el; if(el!=0){ t[nd]=el; leaf[nd]=true; return; } t[nd]=-1; adj[nd][0]=++cur; oku(cur); adj[nd][1]=++cur; oku(cur); } int inv[MAXN]; void merge(inset& ata, inset& a, inset& b,int nd,int sol,int sag){ if(a.size()<b.size()) a.swap(b); int bir=0; int iki=0; int sz=a.size(); for(auto el:b){ auto deg=a.order_of_key(el); bir+=deg; iki+=sz-deg; } for(auto el:b) a.insert(el); a.swap(ata); inv[nd]=inv[sol]+inv[sag]+min(bir,iki); } inset dfs(int nd,int ata){ inset s; if(leaf[nd]){ //DEBUG(nd); s.insert(t[nd]); return s; } auto bir=dfs(adj[nd][0],ata); auto iki=dfs(adj[nd][1],ata); merge(s,bir,iki,nd,adj[nd][0],adj[nd][1]); return s; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; cur=1; oku(1); dfs(1,0); cout<<inv[1]<<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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...