| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 863434 | 2023-10-20T10:47:29 Z | vjudge1 | Tree Rotations (POI11_rot) | C++17 | 101 ms | 65536 KB |
//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define file(s) if(fopen(s".in","r")) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()
#define tm (tl + tr >> 1)
#define ls v << 1, tl, tm
#define rs v << 1 | 1, tm + 1, tr
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define elif else if
#define F first
#define S second
#define int long long
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef long double ld;
const int MOD = 1e9 + 7;
const int N = 1e6 + 7;
const int P = 911;
const ll INF = 1e18;
int rnd() {
int x = rand() << 15;
return x ^ rand();
}
vector <int> g[N];
int sz[N], res[N], ans, cnt[N], a[N], n, t[N << 2];
int id[N];
vector <int> vc[N];
void upd(int idx, int val, int v = 1, int tl = 0, int tr = n + 1) {
if (tl == tr) {
t[v] += val;
return;
}
if (idx <= tm) upd(idx, val, ls);
else upd(idx, val, rs);
t[v] = t[v << 1] + t[v << 1 | 1];
}
int get(int l, int r, int v = 1, int tl = 0, int tr = n + 1) {
if (tl > tr) return 0;
if (l <= tl && tr <= r) {
return t[v];
}
elif (r < tl || tr < l) return 0;
return get(l, r, ls) + get(l, r, rs);
}
void calc(int v = 1, int pr = 0) {
id[v] = v;
sz[v] = 1;
for (int u: g[v]) if (u != pr) {
calc(u, v);
sz[v] += sz[u];
}
}
void add(int v) {
if (!a[v]) return;
upd(a[v], 1);
}
void clr(int v) {
if (!a[v]) return;
upd(a[v], -1);
}
void dadd(int v) {
add(v);
for (int u: g[v]) {
dadd(u);
}
}
void dclr(int v) {
clr(v);
for (int u: g[v]) {
dclr(u);
}
}
void dfs(int v = 1, bool act = 0) {
int to = 0;
for (int u: g[v]) {
// cout << "dd " << v << ' ' << u << '\n';
if (sz[u] > sz[to]) {
to = u;
}
}
for (int u: g[v]) {
if (u != to) {
dfs(u, 1);
id[v] = id[u];
}
}
if (to) dfs(to, 0);
int cur1 = 0, cur2 = 0;
// cout << "ans " << v << '\n';
for (int it: vc[id[v]]) {
cur1 += get(it + 1, n);
cur2 += get(1, it - 1);
if (id[to]) vc[id[to]].pb(it);
// cout << it << ' ' << cur1 << ' ' << cur2 << '\n';
}
if (to) id[v] = id[to];
ans += min(cur1, cur2);
if (a[v]) {
// cout << v << ' ' << a[v] << ' ' << id[v] << '\n';
vc[id[v]].pb(a[v]);
}
add(v);
for (int u: g[v]) if (u != to) {
dadd(u);
}
if (act) {
dclr(v);
return;
}
}
int temp = 1;
set <int> st;
map <int, int> mp;
void input(int v) {
int x;
cin >> x;
if (x) {
st.insert(x);
a[v] = x;
return;
}
temp++;
g[v].pb(temp);
input(temp);
temp++;
g[v].pb(temp);
input(temp);
}
void GazizMadi() {
cin >> n;
input(1);
for (int it: st) {
mp[it] = len(mp) + 1;
}
for (int i = 1; i <= temp; i++) {
a[i] = mp[a[i]];
}
calc();
dfs();
cout << ans;
}
const bool Cases = 0;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
srand(time(0));
int TT = 1;
if (Cases) cin >> TT;
for (int i = 1; i <= TT; i++) {
//cout << "Case " << i << ": ";
GazizMadi();
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 11 ms | 58200 KB | Output is correct |
| 2 | Correct | 12 ms | 58204 KB | Output is correct |
| 3 | Correct | 11 ms | 58200 KB | Output is correct |
| 4 | Correct | 11 ms | 58200 KB | Output is correct |
| 5 | Correct | 11 ms | 58204 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 11 ms | 58380 KB | Output is correct |
| 2 | Correct | 12 ms | 58304 KB | Output is correct |
| 3 | Correct | 12 ms | 58204 KB | Output is correct |
| 4 | Correct | 11 ms | 58204 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 13 ms | 58460 KB | Output is correct |
| 2 | Correct | 13 ms | 58456 KB | Output is correct |
| 3 | Correct | 16 ms | 58716 KB | Output is correct |
| 4 | Correct | 12 ms | 58460 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 17 ms | 59484 KB | Output is correct |
| 2 | Correct | 23 ms | 59212 KB | Output is correct |
| 3 | Correct | 17 ms | 59480 KB | Output is correct |
| 4 | Correct | 17 ms | 59484 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 27 ms | 61788 KB | Output is correct |
| 2 | Correct | 52 ms | 61216 KB | Output is correct |
| 3 | Runtime error | 79 ms | 65536 KB | Execution killed with signal 9 |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 101 ms | 65536 KB | Execution killed with signal 9 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 46 ms | 65536 KB | Execution killed with signal 9 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 63 ms | 65536 KB | Execution killed with signal 9 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 47 ms | 65536 KB | Execution killed with signal 9 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 62 ms | 65536 KB | Execution killed with signal 9 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 67 ms | 65536 KB | Execution killed with signal 9 |
| 2 | Halted | 0 ms | 0 KB | - |