Submission #108626

#	Time	Username	Problem	Language	Result	Execution time	Memory
108626		bharat2002	Untitled (POI11_rot)	C++14	63 / 100	568 ms	47784 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int N=2e5 + 100;
#define int long long
int nxt, n, tree[4*N], arr[2*N], ssum[N], ans[N];vector<int> vals[2*N], adjlist[2*N];
void input(int i)
{
	int v;cin>>v;
	if(v==0)
	{
		adjlist[i].push_back(nxt);input(nxt++);adjlist[i].push_back(nxt);input(nxt++);
		ssum[i]=ssum[adjlist[i][0]] + ssum[adjlist[i][1]];
		if(ssum[adjlist[i][0]]>ssum[adjlist[i][1]]) swap(adjlist[i][0], adjlist[i][1]);
	}
	else
	{
		arr[i]=v;ssum[i]=1;return;
	}
}
int valind;
void remove(int i=1, int l=1, int r=n){
	if(tree[i]==0) return;
	if(l==r)
	{
		tree[i]=0;
		vals[valind].push_back(l);
		//cout<<valind<<" "<<l<<endl;
		return;
	}
	int mid=(l+r)>>1;remove(2*i, l, mid);remove(2*i+1, mid+1, r);tree[i]=0;
}
void update(int ql, int qr, int i=1, int l=1, int r=n)
{
	if(l>qr||r<ql) return;
	if(l==r)
	{
		tree[i]=1;return;
	}
	int mid=(l+r)>>1;update(ql, qr, 2*i, l, mid);update(ql, qr, 2*i+1, mid+1, r);
	tree[i]=tree[2*i] + tree[2*i+1];
}
int query(int ql, int qr, int i=1, int l=1, int r=n)
{
	if(l>qr||r<ql) return 0;
	if(l>=ql&&r<=qr) return tree[i];
	int mid=(l+r)>>1;return query(ql, qr, 2*i, l, mid) + query(ql, qr, 2*i+1, mid+1, r);
}
void dfs(int i)
{
	if(adjlist[i].empty())
	{
		ans[i]=0;update(arr[i], arr[i]);return;
	}
	dfs(adjlist[i][0]);valind=adjlist[i][0];remove();
	dfs(adjlist[i][1]);int tans=0;
	for(auto j:vals[adjlist[i][0]])
	{
		tans+=query(1, j-1);
	}
	for(auto j:vals[adjlist[i][0]])
	{
		update(j, j);
	}
	ans[i]=min(tans, ssum[adjlist[i][0]]*ssum[adjlist[i][1]] - tans) + ans[adjlist[i][0]] + ans[adjlist[i][1]];
}
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n;nxt=2;
	input(1);


	dfs(1);
/*	for(int i=1;i<=5;i++)
	{
		cout<<i<<": "<<ans[i]<<endl;
	}*/

	cout<<ans[1];
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10