Submission #1093314

#TimeUsernameProblemLanguageResultExecution timeMemory
1093314asli_bgUntitled (POI11_rot)C++11
0 / 100
32 ms36444 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 adj[MAXN][2]; int t[MAXN*4]; void oku(int nd){ int el; cin>>el; if(el!=0){ t[nd]=el; return; } t[nd]=-1; oku(nd*2); oku(nd*2+1); } int inv[4*MAXN]; inset s[MAXN]; void merge(int nd,int sol,int sag){ //cout<<"here"<<endl; if(s[sol].size()<s[sag].size()) swap(sol,sag); s[nd]=s[sol]; inv[nd]+=inv[sol]; if(t[nd]!=-1) s[sag].insert(t[nd]); //cont(s[sol]); //cont(s[sag]); for(auto el:s[sag]){ inv[nd]=s[nd].size()-s[nd].order_of_key(el); s[nd].insert(el); } } void dfs(int nd,int ata){ if(t[nd]==0) return; dfs(nd*2,ata); dfs(nd*2+1,ata); merge(nd,nd*2,nd*2+1); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; 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...