#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, x, idx = 1, a[1000005], bit[1000005], subtree[1000005], ans[1000005];
vector<int> adj[1000005];
int RES = 0;
set<int> S;
map<int,int> mp;
void add(int pos, int val) {
while(pos <= idx) {
bit[pos] += val;
pos += pos & -pos;
}
}
int get(int x) {
if(x <= 0) return 0;
int res = 0;
for (; x; x-=x&(-x)) res+=bit[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 upd(int u, int tp) {
if(adj[u].empty()) add(a[u], tp);
for (int node: adj[u]) upd(node,tp);
}
void dfs(int u) {
int mx = 0, p = -1, idx;
for (int i = 0; i < adj[u].size(); i++) {
int node = adj[u][i];
if(mx < subtree[node]) mx = subtree[node], p = node, idx = i;
}
if(p == -1) {
add(a[u],1);
return;
}
if(idx == 1) swap(adj[u][0], adj[u][1]);
dfs(adj[u][1]);
upd(adj[u][1], -1);
dfs(p);
pair<int, int> val = dfs2(adj[u][1]);
RES += min(val.first, val.second);
upd(adj[u][1], 1);
}
void solve() {
cin >> n;
build(1);
n = idx;
for (int i = 1; i <= n; i++) if(a[i]) S.insert(a[i]);
int d = 0;
for (int i: S) mp[i] = ++d;
for (int i = 1; i <= n; i++) a[i] = mp[a[i]];
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
rot.cpp: In function 'void dfs(long long int)':
rot.cpp:59:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < adj[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
rot.cpp: In function 'int main()':
rot.cpp:91:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | freopen("input.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
rot.cpp:92:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | freopen("output.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
24116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
24668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
26712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
89 ms |
33304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
43860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
170 ms |
46672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
292 ms |
58412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
257 ms |
60240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
281 ms |
62032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
