# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1067290 | trandangquang | Untitled (POI11_rot) | C++17 | 24 ms | 21336 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define ii pair <int, int>
#define fi first
#define se second
#define eb emplace_back
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
using namespace std;
const int mxN = 5e5+5;
const int mxL = 2e5+5;
int n, val[mxN], cur, ans;
ii ch[mxN];
vector <int> valN[mxN];
int newNode() {
return ++cur;
}
void input(int node) {
int x; cin >> x;
if(x == 0) {
int lfN = newNode();
input(lfN);
int rtN = newNode();
input(rtN);
ch[node] = {lfN, rtN};
}
else {
val[node] = x;
ch[node] = {-1, -1};
}
}
void dfs(int u) {
if(val[u] != 0) valN[u].eb(val[u]);
if(ch[u].fi == -1 || ch[u].se == -1) return;
dfs(ch[u].fi); dfs(ch[u].se);
valN[u].resize(sz(valN[ch[u].fi]) + sz(valN[ch[u].se]));
merge(all(valN[ch[u].fi]), all(valN[ch[u].se]), valN[u].begin());
int lr = 0;
for(int i:valN[ch[u].se]) {
int pos = upper_bound(all(valN[ch[u].fi]), i) - valN[ch[u].fi].begin();
lr += sz(valN[ch[u].fi]) - pos;
}
int rl = 0;
for(int i:valN[ch[u].fi]) {
int pos = upper_bound(all(valN[ch[u].se]), i) - valN[ch[u].se].begin();
rl += sz(valN[ch[u].se]) - pos;
}
ans = ans + min(lr, rl);
}
int main() {
if(fopen("test.inp", "r")) {
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
cin.tie(0)->sync_with_stdio(0);
cin >> n;
cur = 1; input(1);
// dfs(1);
cout << ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |