oj.uz

Submission #870519

# Submission time Handle Problem Language Result Execution time Memory
870519 2023-11-08T07:23:50 Z vjudge1 Tree Rotations (POI11_rot) C++17
72 / 100
 486 ms 28708 KB 
// KCPC - 50.6907
#include <bits/stdc++.h>

#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define rs(v) v << 1 | 1, md + 1, r
#define ls(v) v << 1, l, md
#define md ((l + r) >> 1)
#define pb emplace_back
#define elif else if
#define uns unsigned
#define emp empty()
#define nll nullptr
#define S second
#define F first

using namespace std;

typedef long long ll;
typedef long double ldb;
typedef vector < ll > vll;
typedef vector < int > vi;
typedef pair < ll, ll > pll;
typedef pair < int, int > pi;
typedef pair < ldb, ldb > pldb;
typedef vector < pair < ll, ll > > vpll;
typedef vector < pair < int, int > > vpi;

const int N = 6e5 + 11;
const int M = 1e4 + 123;
const int mod = 1e9 + 7;
const int mxlg = 19;
const int K = 20;
const int P = 31;
const ll inf = 1e9 + 10;

//mt19937 rnd(07062006);

ll n, timer = 1, res;
ll a[N], sz[N], l[N], r[N], t[4 * N];

void add(int k, int x, int v = 1, int l = 1, int r = n){
	if(l == r){
		t[v] += x;
		return;
	}
	if(k <= md) add(k, x, ls(v));
	else add(k, x, rs(v));
	t[v] = t[v << 1] + t[v << 1 | 1];
}

int get(int tl, int tr, int v = 1, int l = 1, int r = n){
	if(r < tl || tr < l) return 0;
	if(tl <= l && r <= tr) return t[v];
	return get(tl, tr, ls(v)) + 
		   get(tl, tr, rs(v));
}

void ans(int v, int &x1, int &x2){
	if(a[v]){
		x1 += get(1, a[v] - 1);
		x2 += get(a[v] + 1, n);
		return;
	}
	ans(l[v], x1, x2);
	ans(r[v], x1, x2);
}

void upd(int v, int x){
	if(a[v]){
		add(a[v], x);
		return;
	}
	upd(l[v], x);
	upd(r[v], x);
}

void dfs(int v, bool cl){
	if(a[v]){
		if(!cl) add(a[v], 1);
		return;
	}
	if(sz[l[v]] > sz[r[v]]) swap(l[v], r[v]);
	dfs(l[v], 1);
	dfs(r[v], 0);
	int x1 = 0, x2 = 0;
	ans(l[v], x1, x2);
	res += min(x1, x2);
	if(cl) upd(r[v], -1);
	else upd(l[v], 1);	
}

void read(int v){
	cin >> a[v], sz[v] = 1;
	if(a[v]) return;
	l[v] = ++timer;
	read(l[v]);
	sz[v] += sz[l[v]];
	r[v] = ++timer;
	read(r[v]);
	sz[v] += sz[r[v]];
}

void output(){
	cin >> n;
	read(1);
	dfs(1, 0);
	cout << res;
}

const bool cases = 0;

signed main(){12
//  file("disrupt");
    adiyer();
    int tt = 1;
    if(cases) cin >> tt;
    for(int i = 1; i <= tt; i++){
//      cout << "Case " << i << ":\n";
        output();
    }
}

Compilation message

rot.cpp: In function 'int main()':
rot.cpp:114:15: warning: statement has no effect [-Wunused-value]
  114 | signed main(){12
      |               ^~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 2 ms 8664 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8796 KB Output is correct
2 Correct 7 ms 8540 KB Output is correct
3 Correct 4 ms 8796 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13404 KB Output is correct
2 Correct 25 ms 12892 KB Output is correct
3 Correct 83 ms 12928 KB Output is correct
4 Correct 16 ms 11608 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 14988 KB Output is correct
2 Correct 60 ms 16220 KB Output is correct
3 Correct 71 ms 16988 KB Output is correct
4 Correct 67 ms 16732 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 19800 KB Output is correct
2 Correct 91 ms 17756 KB Output is correct
3 Correct 127 ms 16216 KB Output is correct
4 Correct 96 ms 17460 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 16988 KB Output is correct
2 Correct 122 ms 18348 KB Output is correct
3 Correct 107 ms 20824 KB Output is correct
4 Correct 109 ms 20604 KB Output is correct

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 24316 KB Output is correct
2 Incorrect 259 ms 28708 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

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