Submission #108543

#	Time	Username	Problem	Language	Result	Execution time	Memory
108543		bharat2002	Untitled (POI11_rot)	C++14	0 / 100	327 ms	49284 KiB

Main

/*input
8
0
0
0
8
7
0
6
5
0
0
4
3
0
2
1
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e5 + 100;
const int mod=1e9 + 7;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
vector<int> adjlist[2*N];int arr[2*N], n;
int pos[2*N], ans[2*N];//vals[pos[i]] gives the set of values for the ith node. 
int cval, nxt;
int tree[4*N];int ssum[2*N];
vector<int> vals[2*N];
void build(int i=1, int l=1, int r=n)
{
	tree[i]=0;
	if(l==r) return;
	int mid=(l+r)>>1;build(2*i, l, mid);build(2*i+1, mid+1, r);
}
int curpos;
void remove(int i=1, int l=1, int r=n)
{
	if(tree[i]==0) return;
	if(l==r)
	{
		
		vals[curpos].push_back(l);tree[i]=0;return;
	}
	tree[i]=0;int mid=(l+r)>>1;remove(2*i, l, mid);remove(2*i+1, mid+1, r);
}
int ql, qr;
void update(int i=1, int l=1, int r=n)
{
	if(l>qr||r<ql) return;
	if(l>=ql&&r<=qr)
	{
		tree[i]=1;return;
	}
	int mid=(l+r)>>1;update(2*i, l, mid);update(2*i+1, mid+1, r);
	tree[i]=tree[2*i] + tree[2*i+1];
}
int query(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(2*i, l, mid) + query(2*i+1, mid+1, r);
}
void dfs(int i)
{
	int v;cin>>v;
	if(v==0)
	{
		adjlist[i].push_back(cval);
		dfs(cval++);
		adjlist[i].push_back(cval);dfs(cval++);ssum[i]=ssum[adjlist[i][1]]+ssum[adjlist[i][0]];
		if(ssum[adjlist[i][0]]>ssum[adjlist[i][1]]) swap(adjlist[i][0], adjlist[i][1]);
	}
	else
	{
		arr[i]=v;ssum[i]=1;
		pos[i]=nxt++;
		return;
	}
}
void mdfs(int i)
{
	if(adjlist[i].empty())
	{
		ans[i]=0;ql=qr=arr[i];update();
		return;
	}
	mdfs(adjlist[i][0]);curpos=adjlist[i][0];
	remove();
	mdfs(adjlist[i][1]);ql=1;qr=n;
	int prevsum=query();int tot=0, prevpos=n;
	reverse(vals[curpos].begin(), vals[curpos].end());
	for(auto j:vals[curpos])
	{
		ql=1;qr=j-1;tot+=query();
	}
	
	if(i==2)
	{
		cout<<curpos<<": ";
		for(auto j:vals[curpos]) cout<<j<<" ";cout<<endl<<endl;
	}
	for(auto j:vals[curpos])
	{
		ql=qr=j;update();
	}
	if(i==2)
	{
		cout<<tree[1]<<endl;
	}
	ans[i]=ans[adjlist[i][0]] + ans[adjlist[i][1]] + min(tot, ssum[adjlist[i][0]]*ssum[adjlist[i][1]] - tot);
}
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n;cval=2;nxt=1;
	dfs(1);
	mdfs(1);
/*	for(int i=1;i<=15;i++) {cout<<i<<": ";//<<ans[i]<<endl;
		for(auto j:vals[i]) cout<<j<<" ";cout<<endl;
//		cout<<" val="<<arr[i]<<endl;
	}*/
	cout<<ans[1];
}

Compilation message (stderr)

rot.cpp: In function 'void mdfs(long long int)':
rot.cpp:105:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(auto j:vals[curpos]) cout<<j<<" ";cout<<endl<<endl;
   ^~~
rot.cpp:105:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(auto j:vals[curpos]) cout<<j<<" ";cout<<endl<<endl;
                                         ^~~~
rot.cpp:95:6: warning: unused variable 'prevsum' [-Wunused-variable]
  int prevsum=query();int tot=0, prevpos=n;
      ^~~~~~~
rot.cpp:95:33: warning: unused variable 'prevpos' [-Wunused-variable]
  int prevsum=query();int tot=0, prevpos=n;
                                 ^~~~~~~

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