oj.uz

Submission #30075

# Submission time Handle Problem Language Result Execution time Memory
30075 2017-07-22T04:47:48 Z 박상수(#1251) Tree Rotations (POI11_rot) C++11
45 / 100
 1000 ms 8408 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int n;
ll ans;
int P[200020], z;
int temp[200020];

void read() {
	int x; scanf("%d", &x);
	if(x == 0) {
		int a = z;
		read();
		int b = z;
		read();
		int nz = 0, j=a+1;
		ll t = 0;
		for(int i=b+1;i<=z;i++) {
			while(j<=b && P[j] < P[i]) temp[nz++] = P[j++];
			t += (b - j + 1);
			temp[nz++] = P[i];
		}
		while(j <= b) temp[nz++] = P[j++];
		t = min(t, ((ll)(z-b) * (b-a) - t));
		ans += t;
		rep(i, nz) P[a+1+i] = temp[i];
	}
	else P[++z] = x;
}

void solve(){
	scanf("%d", &n);
	read();
	printf("%lld\n", ans);
}

int main(){
	int T = 1; // scanf("%d", &T);
	while(T--) {
		solve();
	}
	
	return 0;
}

Compilation message

rot.cpp: In function 'void read()':
rot.cpp:39:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int x; scanf("%d", &x);
                        ^
rot.cpp: In function 'void solve()':
rot.cpp:61:17: 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 3580 KB Output is correct
2 Correct 0 ms 3580 KB Output is correct
3 Correct 0 ms 3580 KB Output is correct
4 Correct 0 ms 3580 KB Output is correct
5 Correct 0 ms 3580 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3648 KB Output is correct
2 Correct 0 ms 3580 KB Output is correct
3 Correct 19 ms 3652 KB Output is correct
4 Correct 19 ms 3692 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 4148 KB Output is correct
2 Correct 6 ms 3580 KB Output is correct
3 Correct 9 ms 3580 KB Output is correct
4 Correct 63 ms 3920 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3580 KB Output is correct
2 Correct 793 ms 4704 KB Output is correct
3 Execution timed out 1000 ms 5560 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 8408 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 3644 KB Output is correct
2 Execution timed out 1000 ms 4780 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 6024 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 4504 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 4240 KB Execution timed out
2 Halted 0 ms 0 KB -