Submission #870520

#	Time	Username	Problem	Language	Result	Execution time	Memory
870520		vjudge1	Untitled (POI11_rot)	C++17	100 / 100	749 ms	32616 KiB

Main

// 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 (stderr)

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

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 10 / 10