oj.uz

Submission #30098

# Submission time Handle Problem Language Result Execution time Memory
30098 2017-07-22T05:58:43 Z 김동현(#1246) Tree Rotations (POI11_rot) C++14
45 / 100
 1000 ms 21780 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, a[400010], c = 1, lc[400010], rc[400010];
ll ans;

vector<int> f(int r){
	if(a[c]){
		vector<int> ret;
		ret.push_back(a[c]);
		return ret;
	}
	vector<int> lv = f(++c);
	vector<int> rv = f(++c);
	vector<int> ret;
	ll li = 0, ri = 0;
	for(int i = 0, j = 0; i < lv.size() || j < rv.size(); ){
		if(i == lv.size()){
			li += int(lv.size());
			ret.push_back(rv[j++]);
		}
		else if(j == rv.size()){
			ri += int(rv.size());
			ret.push_back(lv[i++]);
		}
		else{
			if(lv[i] < rv[j]){
				ri += j;
				ret.push_back(lv[i++]);
			}
			else{
				li += i;
				ret.push_back(rv[j++]);
			}
		}
	}
	ans += min(li, ri);
	return ret;
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i < 2 * n; i++) scanf("%d", a + i);
	f(1);
	printf("%lld\n", ans);
}

Compilation message

rot.cpp: In function 'std::vector<int> f(int)':
rot.cpp:18:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0, j = 0; i < lv.size() || j < rv.size(); ){
                          ^
rot.cpp:18:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0, j = 0; i < lv.size() || j < rv.size(); ){
                                           ^
rot.cpp:19:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i == lv.size()){
        ^
rot.cpp:23:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if(j == rv.size()){
             ^
rot.cpp: In function 'int main()':
rot.cpp:43:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
rot.cpp:44:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i < 2 * n; i++) scanf("%d", a + i);
                                                   ^

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 7240 KB Output is correct
2 Correct 3 ms 6840 KB Output is correct
3 Correct 19 ms 7236 KB Output is correct
4 Correct 29 ms 7352 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 8844 KB Output is correct
2 Correct 13 ms 7048 KB Output is correct
3 Correct 16 ms 7076 KB Output is correct
4 Correct 96 ms 8096 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7460 KB Output is correct
2 Correct 996 ms 10792 KB Output is correct
3 Execution timed out 1000 ms 13416 KB Execution timed out
4 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 21780 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 9100 KB Output is correct
2 Execution timed out 1000 ms 12600 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 15264 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 10028 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 10108 KB Execution timed out
2 Halted 0 ms 0 KB -