oj.uz

Submission #30067

# Submission time Handle Problem Language Result Execution time Memory
30067 2017-07-22T04:24:18 Z gs14004 Tree Rotations (POI11_rot) C++14
0 / 100
 169 ms 8408 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 a[MAXN], n, cnt;

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;

lint solve(int s, int m, int e){
	lint ans = 0;
	if(e - m > m - s){
		for(int j=s; j<m; j++) bit.add(a[j], -1);
		for(int j=s; j<m; j++) ans += bit.query(a[j] - 1);
		for(int j=s; j<m; j++) bit.add(a[j], 1);
	}
	else{
		for(int j=m; j<e; j++) bit.add(a[j], -1);
		for(int j=m; j<e; j++) ans += m - s - bit.query(a[j]);
		for(int j=m; j<e; j++) bit.add(a[j], 1);
	}
	return ans;
}

lint solve(){
	int x;
	scanf("%d",&x);
	lint ans = 0;
	if(x == 0){
		int s = cnt;
		ans += solve();
		int m = cnt;
		ans += solve();
		int e = cnt;
		lint tmp = solve(s, m, e);
		ans += min(tmp, 1ll * (e - m) * (m - s) - tmp);
	}
	else{
		bit.add(x, 1);
		a[cnt++] = x;
	}
	return ans;
}

int main(){
	scanf("%d",&n);
	printf("%lld\n", solve());
}

Compilation message

rot.cpp: In function 'lint solve()':
rot.cpp:42: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:61:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^

Subtask #1
0 / 9.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 9.0

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

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 10.0

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