#include "collapse.h"
using namespace std;
typedef vector<int> vi;
const int N = 100000, M = 100000, Q = 100000, K = M + Q, N_ = N + M + 1;
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int n;
int ii[M], jj[M], hh[M], m;
int aa[Q], bb[Q], ans[Q], q;
int ll[K], rr[K], hh_[K], gg[K];
int compare(int h1, int h2) {
return ii[h1] != ii[h2] ? ii[h1] - ii[h2] : (jj[h1] != jj[h2] ? jj[h1] - jj[h2] : h1 - h2);
}
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(hh[j], h);
if (c == 0)
j++;
else if (c < 0) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
}
sort(hh, l, i);
l = k;
}
}
int tt[N_][2], pp[N_], ww[N_], mx[N_]; char lz[N_];
int dir(int u) {
return u == tt[pp[u]][0] ? 0 : 1;
}
int is_root(int u) {
return tt[pp[u]][dir(u)] != u;
}
void put(int u) {
if (u) {
int tmp;
tmp = tt[u][0], tt[u][0] = tt[u][1], tt[u][1] = tmp;
lz[u] ^= 1;
}
}
void pus(int u) {
if (lz[u])
put(tt[u][0]), put(tt[u][1]), lz[u] = 0;
}
void pul(int u) {
if (!lz[u])
mx[u] = max(max(mx[tt[u][0]], ww[u]), mx[tt[u][1]]);
}
int argmax(int u) {
while (1) {
pus(u);
if (mx[u] == ww[u])
return u;
else
u = mx[u] == mx[tt[u][0]] ? tt[u][0] : tt[u][1];
}
}
void attach(int u, int v, int d) {
if (u)
tt[u][d] = v, pul(u);
if (v)
pp[v] = u;
}
void rotate(int u) {
int v = pp[u], w = pp[v], du = dir(u), dv = dir(v), special = is_root(v);
pus(w), pus(v), pus(u);
attach(v, tt[u][du ^ 1], du);
attach(u, v, du ^ 1);
if (special)
pp[u] = w;
else
attach(w, u, dv);
}
void splay(int u) {
while (!is_root(u)) {
int v = pp[u];
if (is_root(v))
rotate(u);
else
rotate(dir(u) == dir(v) ? v : u), rotate(u);
}
}
void expose(int u) {
for (int u_ = u, v = 0; u_; v = u_, u_ = pp[u_])
splay(u_), pus(u_), attach(u_, v, 1);
splay(u), put(u);
}
void link(int u, int v) {
expose(v), expose(u);
pp[v] = u;
}
void cut(int u, int v) {
expose(v), expose(u);
pus(u), attach(u, 0, 1);
pp[v] = 0;
}
int argmax_(int u, int v) {
expose(v), expose(u);
return pp[v] == 0 ? -1 : argmax(u) - n - 1;
}
int ft[N];
void update(int i, int x) {
while (i < n) {
ft[i] += x;
i |= i + 1;
}
}
int query(int i) {
int x = 0;
while (i >= 0) {
x += ft[i];
i &= i + 1, i--;
}
return x;
}
void link_(int h) {
link(ii[h] + 1, n + 1 + h), link(jj[h] + 1, n + 1 + h);
update(jj[h], 1);
}
void cut_(int h) {
cut(ii[h] + 1, n + 1 + h), cut(jj[h] + 1, n + 1 + h);
update(jj[h], -1);
}
int hh1[M], hh2[M], cnt;
void add(int h) {
int h_ = argmax_(ii[h] + 1, jj[h] + 1);
if (h_ == -1 || ww[h_] < ww[h]) {
hh1[cnt] = h_, hh2[cnt] = h, cnt++;
if (h_ != -1)
cut_(h_);
link_(h);
} else
hh1[cnt] = -1, hh2[cnt] = -1, cnt++;
}
void undo() {
int h1 = hh1[cnt - 1], h2 = hh2[cnt - 1];
cnt--;
if (h2 != -1) {
cut_(h2);
if (h1 != -1)
link_(h1);
}
}
void solve(int *gg, int k, int l, int r) {
int g1 = 0, g2 = 0, g3 = k, tmp;
while (g2 < g3)
if (ll[gg[g2]] <= l && r <= rr[gg[g2]])
g2++;
else if (ll[gg[g2]] < r && l < rr[gg[g2]]) {
tmp = gg[g1], gg[g1] = gg[g2], gg[g2] = tmp;
g1++, g2++;
} else {
g3--;
tmp = gg[g2], gg[g2] = gg[g3], gg[g3] = tmp;
}
for (int g = g1; g < g2; g++) {
int g_ = gg[g];
if (hh_[g_] == -1)
add(ll[g_]);
}
if (r - l > 1) {
int m = (l + r) / 2;
solve(gg, g1, l, m), solve(gg, g1, m, r);
} else
for (int g = g1; g < g2; g++) {
int g_ = gg[g], h_ = hh_[g_];
if (h_ != -1)
ans[h_] -= query(bb[h_]);
}
for (int g = g2 - 1; g >= g1; g--) {
int g_ = gg[g];
if (hh_[g_] == -1)
undo();
}
}
vi simulateCollapse(int n_, vi xx, vi ii_, vi jj_, vi aa_, vi bb_) {
n = n_, m = ii_.size(), q = aa_.size();
for (int h = 0; h < m; h++) {
ii[h] = ii_[h], jj[h] = jj_[h];
if (ii[h] > jj[h]) {
int tmp;
tmp = ii[h], ii[h] = jj[h], jj[h] = tmp;
}
}
for (int h = 0; h < m; h++)
hh[h] = h;
sort(hh, 0, m);
int k = 0;
for (int h = 0; h < m; h++)
if (h + 1 < m && ii[hh[h + 1]] == ii[hh[h]] && jj[hh[h + 1]] == jj[hh[h]])
ll[k] = hh[h], rr[k] = hh[h + 1], hh_[k] = -1, k++, h++;
else
ll[k] = hh[h], rr[k] = m, hh_[k] = -1, k++;
for (int h = 0; h < q; h++) {
aa[h] = aa_[h], bb[h] = bb_[h];
ans[h] = n;
ll[k] = aa[h], rr[k] = aa[h] + 1, hh_[k] = h, k++;
}
for (int r = 0; r < 2; r++) {
for (int h = 0; h < m; h++)
ww[n + 1 + h] = jj[h] + 1;
for (int g = 0; g < k; g++)
gg[g] = g;
solve(gg, k, 0, m);
for (int h = 0; h < m; h++) {
int tmp;
tmp = n - 1 - ii[h], ii[h] = n - 1 - jj[h], jj[h] = tmp;
}
for (int h = 0; h < q; h++)
bb[h] = n - 2 - bb[h];
}
return vi(ans, ans + q);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
976 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
5428 KB |
Output is correct |
| 2 |
Correct |
39 ms |
5416 KB |
Output is correct |
| 3 |
Execution timed out |
15067 ms |
10700 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
5460 KB |
Output is correct |
| 2 |
Incorrect |
34 ms |
5448 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
976 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
