oj.uz

Submission #108520

# Submission time Handle Problem Language Result Execution time Memory
108520 2019-04-30T06:38:55 Z bharat2002 Tree Rotations (POI11_rot) C++14
0 / 100
 317 ms 50664 KB 
/*input
3
0
0
3
1
2
*/
#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();
	}
	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);
	cout<<ans[1];
}

Compilation message

rot.cpp: In function 'void mdfs(long long int)':
rot.cpp:85:6: warning: unused variable 'prevsum' [-Wunused-variable]
  int prevsum=query();int tot=0, prevpos=n;
      ^~~~~~~
rot.cpp:85:33: warning: unused variable 'prevpos' [-Wunused-variable]
  int prevsum=query();int tot=0, prevpos=n;
                                 ^~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 19132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 19200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 19328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 19912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 21444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 27008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 35692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 181 ms 37488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 267 ms 48204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 317 ms 49384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 300 ms 50664 KB Output isn't correct
2 Halted 0 ms 0 KB -