oj.uz

Submission #30073

# Submission time Handle Problem Language Result Execution time Memory
30073 2017-07-22T04:39:51 Z 구사과(#1250) Tree Rotations (POI11_rot) C++14
100 / 100
 239 ms 14488 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<lint, lint> pi;
const int MAXN = 200005;

int n;

struct bit{
	int tree[MAXN];
	void add(int x, int v){
		while(x <= n){
			tree[x] += v;
			x += x & -x;
		}
	}
	int query(int x){
		int ret = 0;
		while(x) ret += tree[x], x -= x & -x;
		return ret;
	}
}bit;

int cnt, node;
int l[2 * MAXN], r[2 * MAXN];
int st[2 * MAXN], ed[2 * MAXN];
int a[MAXN];

void read_tree(int v){
	int x;
	scanf("%d",&x);
	st[v] = cnt;
	if(x == 0){
		l[v] = ++node;
		read_tree(node);
		r[v] = ++node;
		read_tree(node);
	}
	else{
		a[cnt++] = x;
	}
	ed[v] = cnt;
}

lint dfs(int v){
	if(ed[v] - st[v] == 1){
		bit.add(a[st[v]], 1);
		return 0;
	}
	int ls = ed[l[v]] - st[l[v]];
	int rs = ed[r[v]] - st[r[v]];
	lint ans1 = 0, ans2 = 0;
	if(ls < rs){
		ans1 += dfs(l[v]);
		for(int i=st[l[v]]; i<ed[l[v]]; i++){
			bit.add(a[i], -1);
		}
		ans1 += dfs(r[v]);
		for(int i=st[l[v]]; i<ed[l[v]]; i++){
			ans2 += bit.query(a[i]);
		}
		for(int i=st[l[v]]; i<ed[l[v]]; i++){
			bit.add(a[i], 1);
		}
	}
	else{
		ans1 += dfs(r[v]);
		for(int i=st[r[v]]; i<ed[r[v]]; i++){
			bit.add(a[i], -1);
		}
		ans1 += dfs(l[v]);
		for(int i=st[r[v]]; i<ed[r[v]]; i++){
			ans2 += ls - bit.query(a[i]);
		}
		for(int i=st[r[v]]; i<ed[r[v]]; i++){
			bit.add(a[i], 1);
		}
	}
	return ans1 + min(1ll * ls * rs - ans2, ans2);
}

int main(){
	scanf("%d",&n);
	read_tree(0);
	printf("%lld",dfs(0));
}

Compilation message

rot.cpp: In function 'void read_tree(int)':
rot.cpp:32:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&x);
                ^
rot.cpp: In function 'int main()':
rot.cpp:84:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9832 KB Output is correct
2 Correct 0 ms 9832 KB Output is correct
3 Correct 0 ms 9832 KB Output is correct
4 Correct 0 ms 9832 KB Output is correct
5 Correct 0 ms 9832 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9832 KB Output is correct
2 Correct 0 ms 9832 KB Output is correct
3 Correct 0 ms 9832 KB Output is correct
4 Correct 0 ms 9832 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9832 KB Output is correct
2 Correct 0 ms 9832 KB Output is correct
3 Correct 0 ms 9832 KB Output is correct
4 Correct 0 ms 9832 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9852 KB Output is correct
2 Correct 0 ms 9832 KB Output is correct
3 Correct 0 ms 9852 KB Output is correct
4 Correct 0 ms 9884 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10224 KB Output is correct
2 Correct 6 ms 9832 KB Output is correct
3 Correct 29 ms 9832 KB Output is correct
4 Correct 6 ms 10056 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9832 KB Output is correct
2 Correct 19 ms 10644 KB Output is correct
3 Correct 19 ms 11288 KB Output is correct
4 Correct 33 ms 11164 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13420 KB Output is correct
2 Correct 36 ms 11780 KB Output is correct
3 Correct 56 ms 10728 KB Output is correct
4 Correct 36 ms 10032 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9844 KB Output is correct
2 Correct 59 ms 10700 KB Output is correct
3 Correct 53 ms 12576 KB Output is correct
4 Correct 43 ms 12444 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 11636 KB Output is correct
2 Correct 113 ms 10724 KB Output is correct
3 Correct 93 ms 11068 KB Output is correct
4 Correct 123 ms 10496 KB Output is correct
5 Correct 189 ms 9832 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 10552 KB Output is correct
2 Correct 103 ms 13836 KB Output is correct
3 Correct 136 ms 12584 KB Output is correct
4 Correct 89 ms 14488 KB Output is correct
5 Correct 229 ms 9832 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 10292 KB Output is correct
2 Correct 109 ms 10904 KB Output is correct
3 Correct 173 ms 9832 KB Output is correct
4 Correct 153 ms 10292 KB Output is correct
5 Correct 103 ms 14396 KB Output is correct
6 Correct 239 ms 9832 KB Output is correct