oj.uz

Submission #870520

# Submission time Handle Problem Language Result Execution time Memory
870520 2023-11-08T07:24:23 Z vjudge1 Tree Rotations (POI11_rot) C++17
100 / 100
 749 ms 32616 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
#define int long long

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:115:15: warning: statement has no effect [-Wunused-value]
  115 | signed main(){12
      |               ^~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8536 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 8660 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 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 8796 KB Output is correct
3 Correct 4 ms 8796 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13660 KB Output is correct
2 Correct 23 ms 12892 KB Output is correct
3 Correct 75 ms 12924 KB Output is correct
4 Correct 15 ms 11356 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 14984 KB Output is correct
2 Correct 58 ms 16476 KB Output is correct
3 Correct 67 ms 17488 KB Output is correct
4 Correct 63 ms 17204 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 21172 KB Output is correct
2 Correct 91 ms 18440 KB Output is correct
3 Correct 123 ms 16464 KB Output is correct
4 Correct 80 ms 17500 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 17244 KB Output is correct
2 Correct 117 ms 18516 KB Output is correct
3 Correct 102 ms 21584 KB Output is correct
4 Correct 104 ms 21588 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 26224 KB Output is correct
2 Correct 244 ms 26192 KB Output is correct
3 Correct 217 ms 26668 KB Output is correct
4 Correct 283 ms 25680 KB Output is correct
5 Correct 562 ms 24408 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 24412 KB Output is correct
2 Correct 240 ms 30088 KB Output is correct
3 Correct 285 ms 29780 KB Output is correct
4 Correct 190 ms 32616 KB Output is correct
5 Correct 693 ms 24804 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 23988 KB Output is correct
2 Correct 214 ms 26836 KB Output is correct
3 Correct 508 ms 24912 KB Output is correct
4 Correct 303 ms 25428 KB Output is correct
5 Correct 172 ms 32428 KB Output is correct
6 Correct 749 ms 24916 KB Output is correct