#include <bits/stdc++.h>
namespace std
{
template <class Fun>
class y_combinator_result
{
Fun fun_;
public:
template <class T>
explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
template <class... Args>
decltype(auto) operator()(Args &&... args)
{
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template <class Fun>
decltype(auto) y_combinator(Fun &&fun)
{
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
} // namespace std
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<pll> vll;
typedef vector<vl> vvl;
#define fori(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i >= 0; i--)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repd(i, a, b) for (int i = a; i >= b; i--)
#define trav(x, a) for (auto &x : a)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define sz(a) (int)(a).size()
#define fi first
#define se second
clock_t time_p = clock();
void time_taken()
{
time_p = clock() - time_p;
cerr << "Time Taken : " << (float)(time_p) / CLOCKS_PER_SEC << "\n";
}
const ll mod = 1e9 + 7;
const ll INF = 1e18;
#include <bits/extc++.h>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// s.order_of_key(x) -> Number of elements in s strictly smaller than x
// auto it = s.find_by_order(k) -> iterator to the kth smallest element(0-indexed)
struct BIT
{
vector<int> bit;
BIT(int n = 1e5 + 6) : bit(n)
{
}
void update(int x, int v)
{
while (x < int(bit.size()))
{
bit[x] += v;
x += (x & -x);
}
}
int query(int x)
{
int sum = 0;
while (x > 0)
{
sum += bit[x];
x -= (x & -x);
}
return sum;
}
void upd_range(int l, int r, int v)
{
update(l, v);
update(r + 1, -v);
}
long long query_range(int l, int r)
{
return query(r) - query(l - 1);
}
};
int main()
{
// ios_base::sync_with_stdio(false), cin.tie(nullptr);
int n;
scanf("%d", &n);
array<int, 2> adj[2 * n + 10];
vi sub(2 * n + 10), val(2 * n + 10);
BIT b(n + 10);
ll ans = 0;
int cur = 0;
function<int()> read = [&]() -> int {
int p;
scanf("%d", &p);
int me = cur++;
val[me] = p;
sub[me] = 1;
if (p)
{
return 1;
}
adj[me][0] = cur;
sub[me] += read();
adj[me][1] = cur;
sub[me] += read();
return sub[me];
};
read();
function<vi(int, bool)> go = [&](int u, bool keep) -> vi {
vi ret;
if (val[u])
{
if (keep)
b.update(val[u], 1);
ret.pb(val[u]);
return ret;
}
bool fl = (sub[adj[u][0]] > sub[adj[u][1]]);
if (fl)
{
ll i1 = 0, i2 = 0;
auto v1 = go(adj[u][1], false);
auto v2 = go(adj[u][0], true);
ret = v2;
for (int x : v1)
{
ret.pb(x);
int lt = b.query(x);
int gt = sz(v2) - lt;
i1 += lt;
i2 += gt;
}
for (int x : v1)
b.update(x, 1);
ans += min(i1, i2);
}
else
{
ll i1 = 0, i2 = 0;
auto v1 = go(adj[u][0], false);
auto v2 = go(adj[u][1], true);
ret = v2;
for (int x : v1)
{
ret.pb(x);
int lt = b.query(x);
int gt = sz(v2) - lt;
i1 += lt;
i2 += gt;
}
for (int x : v1)
b.update(x, 1);
ans += min(i1, i2);
}
if (!keep)
{
for (auto x : ret)
b.update(x, -1);
}
return ret;
};
go(0, 1);
printf("%lld\n", ans);
return 0;
}
Compilation message
rot.cpp: In function 'int main()':
rot.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
113 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
rot.cpp: In lambda function:
rot.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
125 | scanf("%d", &p);
| ~~~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
1132 KB |
Output is correct |
2 |
Correct |
3 ms |
620 KB |
Output is correct |
3 |
Correct |
6 ms |
1152 KB |
Output is correct |
4 |
Correct |
7 ms |
1260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
2796 KB |
Output is correct |
2 |
Correct |
10 ms |
1132 KB |
Output is correct |
3 |
Correct |
27 ms |
2028 KB |
Output is correct |
4 |
Correct |
20 ms |
2412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
43 ms |
2864 KB |
Output is correct |
2 |
Correct |
144 ms |
6124 KB |
Output is correct |
3 |
Correct |
244 ms |
8688 KB |
Output is correct |
4 |
Correct |
262 ms |
9024 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1041 ms |
17772 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
172 ms |
7848 KB |
Output is correct |
2 |
Execution timed out |
1046 ms |
11444 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
461 ms |
15212 KB |
Output is correct |
2 |
Correct |
539 ms |
15216 KB |
Output is correct |
3 |
Correct |
317 ms |
14140 KB |
Output is correct |
4 |
Correct |
472 ms |
13124 KB |
Output is correct |
5 |
Correct |
175 ms |
8468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
593 ms |
12680 KB |
Output is correct |
2 |
Execution timed out |
1036 ms |
23532 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
582 ms |
11268 KB |
Output is correct |
2 |
Execution timed out |
1093 ms |
16476 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |