Submission #1020520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020520		toan2602	Untitled (POI11_rot)	C++17	0 / 100	1071 ms	21840 KiB

Main

#include<bits/stdc++.h>

using namespace std;
int n, x, idx = 1, a[400005], bit[400005], subtree[400005], ans[400005];
vector<int> adj[400005];
int RES = 0;
void add(int pos, int val) {
	while(pos <= idx) {
		bit[pos] += val;
		pos += pos & -pos;
	}
}

int get(int x) {
	int res = 0;
	while(x > 0) {
		res += bit[x];
		x -= x & -x;
	}
	return res;
}
int range(int l, int r) {return get(r) - get(l-1);}
void build_sub(int u, int par) {
	subtree[u] = 1;
	for (int node: adj[u]) {
		if(node == par) continue;
		build_sub(node, u);
		subtree[u] += subtree[node];
	}
}
void build(int u) {
	cin >> x;
	if(x == 0) {
		int l, r;
		l = idx+1, r = idx+2;
		idx+=2;
		adj[u].push_back(l);
		adj[u].push_back(r);
		build(l);
		build(r);
	}
	else if(adj[u].size() == 0) a[u] = x;
}

pair<int,int> dfs2(int u) {
	pair<int, int> res = {range(a[u]+1,idx), range(1,a[u]-1)};
	for (int node: adj[u]) {pair<int, int> val = dfs2(node); res.first+=val.first,res.second+=val.second;}
	return res;
}

void dfs(int u) {
	int mx = 0, p = 0;
	for (int node: adj[u]) if(mx < subtree[node]) mx = subtree[node], p = node;
	if(p == 0) {
		add(a[u],1);
		return;
	}
	dfs(p);
	if(p == 1) swap(adj[u][0], adj[u][1]), p = 0;
	pair<int, int> val = dfs2(adj[u][1]);
	RES += min(val.first, val.second);
	dfs(adj[u][1]);
}
void solve() {
	cin >> n;
 	build(1);
	n = idx;
	build_sub(1,-1);
	dfs(1);
	cout << RES;
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen("input.inp","r")){
		freopen("input.inp", "r", stdin);
		freopen("output.out", "w", stdout);
	}
	int t = 1;
	// cin >> t;
	while(t--) {
		solve();
	}
}

Compilation message (stderr)

rot.cpp: In function 'int main()':
rot.cpp:76:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   freopen("input.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
rot.cpp:77:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   freopen("output.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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