Submission #1020730

#TimeUsernameProblemLanguageResultExecution timeMemory
1020730kustizusUntitled (POI11_rot)C++17
0 / 100
22 ms9936 KiB
// #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,fma,bmi2,popcnt,lzcnt") #include <bits/stdc++.h> #define int long long using namespace std; mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); const int N=2e5; vector <int> v; pair <int,int> mp[2*N+5]; int n,x,idx=0,cnt[2*N+5],sz[2*N+5],sum[2*N+5],FT[N+5]; void Back(int pos){ if (!v.back()){ v.pop_back(); if (!mp[pos].first){ mp[pos].first=++idx; Back(idx); Back(pos); return; } else mp[pos].second=++idx; Back(idx); } else{ if (!mp[pos].first){ cnt[idx]=v.back(); v.pop_back(); } else{ mp[pos].second=++idx; cnt[idx]=v.back(); v.pop_back(); } } } void dfs(int i){ if (cnt[i]){ sz[i]=1; return; } int x=mp[i].first; int y=mp[i].second; sz[i]=sz[x]+sz[y]; } void Update(int pos, int val){ for (;pos<=n;pos+=pos&(-pos)) FT[pos]+=val; } int Get(int pos){ int val=0; for (;pos;pos-=pos&(-pos)) val+=FT[pos]; return val; } void cl(int i, int val){ if (cnt[i]){ Update(cnt[i],val); return; } int x=mp[i].first; int y=mp[i].second; cl(x,val); cl(y,val); } int lh,nh; void Cal(int i){ if (cnt[i]){ lh+=Get(cnt[i]); nh+=Get(n)-Get(cnt[i]); return; } int x=mp[i].first; int y=mp[i].second; Cal(x); Cal(y); } void dfs1(int i){ if (cnt[i]){ Update(cnt[i],1); return; } int x=mp[i].first; int y=mp[i].second; if (sz[x]>sz[y]) swap(x,y); dfs1(x); sum[i]+=sum[x]; cl(x,-1); dfs1(y); sum[i]+=sum[y]; lh=nh=0; Cal(x); cl(x,1); sum[i]+=min(lh,nh); } void Solve(){ cin>>n; while (cin>>x) v.push_back(x); reverse(v.begin(),v.end()); Back(0); dfs(0); dfs1(0); cout<<sum[0]; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen ("FILE.INP","r",stdin); // freopen ("FILE.OUT","w",stdout); int t=1; // cin>>t; while (t--) Solve(); cerr<<"\nTIME: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n"; }
#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...