#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
const int len = 1e5+5;
struct segment_tree{
int tree[4*len];
segment_tree(){}
void prop(int p, int l, int r){
if (!tree[p] || l == r) return;
tree[2*p] += tree[p];
tree[2*p+1] += tree[p];
tree[p] = 0;
}
void upd(int p, int l, int r, int i, int j, int x){
prop(p, l, r);
if (r < i || j < l)
return;
if (i <= l && r <= j)
tree[p] += x;
else{
int mid = (l+r)/2;
upd(2*p, l, mid, i, j, x);
upd(2*p+1, mid+1, r, i, j, x);
}
}
int ask(int p, int l, int r, int i){
prop(p, l, r);
if (l == r)
return tree[p];
int mid = (l+r)/2;
if (i <= mid)
return ask(2*p, l, mid, i);
return ask(2*p+1, mid+1, r, i);
}
};
segment_tree pref, suf;
int out[len], sz[len], par[len], n, m, q;
vector<ii> oper[4*len], st, todo[len];
map<ii, int> mym;
int fin(int i){
if (par[i] == i) return i;
return fin(i);
}
void print(segment_tree cur){
for (int i = 0; i < n; i++)
printf("%d ", cur.ask(1, 0, n-1, i));
printf("\n");
}
void join(int i, int j){
if (sz[i] > sz[j])
par[j] = i, sz[i] += sz[j];
else
par[i] = j, sz[j] += sz[i];
}
void split(int i, int j){
if (sz[i] > sz[j])
par[j] = j, sz[i] -= sz[j];
else
par[i] = i, sz[j] -= sz[i];
}
void add(int p, int l, int r, int i, int j, ii v){
if (r < i || j < l)
return;
if (i <= l && r <= j)
oper[p].pb(v);
else{
int mid = (l+r)/2;
add(2*p, l, mid, i, j, v);
add(2*p+1, mid+1, r, i, j, v);
}
}
void solve(int p, int l, int r){
for (int i = 0; i < oper[p].size(); i++){
int a = oper[p][i].fi, b = oper[p][i].se, x = fin(a), y = fin(b);
if (x == y){
oper[p][i].fi = -1;
}
else{
pref.upd(1, 0, n-1, b, n-1, -1);
suf.upd(1, 0, n-1, 0, a, -1);
st.pb(mp(x, y));
join(x, y);
}
}
if (l == r){
for (int i = 0; i < todo[l].size(); i++){
int j = todo[l][i].fi, d = todo[l][i].se;
out[d] = pref.ask(1, 0, n-1, j)+suf.ask(1, 0, n-1, j+1);
}
//printf("time = %d\n", l);
//printf("pref = "), print(pref);
//printf("suf = "), print(suf);
}
else{
int mid = (l+r)/2;
solve(2*p, l, mid);
solve(2*p+1, mid+1, r);
}
for (int i = (int)oper[p].size()-1; i >= 0; i--){
if (oper[p][i].fi == -1)
continue;
int a = oper[p][i].fi, b = oper[p][i].se;
pref.upd(1, 0, n-1, b, n-1, 1);
suf.upd(1, 0, n-1, 0, a, 1);
split(st.back().fi, st.back().se);
st.pop_back();
}
oper[p].clear();
}
vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P){
n = N, m = T.size(), q = W.size();
for (int i = 0; i < n; i++){
par[i] = i;
sz[i] = 1;
pref.upd(1, 0, n-1, i, i, i+1);
suf.upd(1, 0, n-1, i, i, n-i);
}
for (int i = 0; i < m; i++){
todo[i].clear();
}
mym.clear();
for (int i = 0; i < m; i++){
int t = T[i], x = X[i], y = Y[i];
if (x > y)
swap(x, y);
if (t == 0)
mym[mp(x, y)] = i;
else{
add(1, 0, m-1, mym[mp(x, y)], i-1, mp(x, y));
mym.erase(mp(x, y));
}
}
for (auto &it: mym)
add(1, 0, m-1, it.se, m-1, it.fi);
for (int i = 0; i < q; i++){
int d = W[i], p = P[i];
todo[d].pb(mp(p, i));
}
solve(1, 0, m-1);
vector<int> out2(q, 0);
for (int i = 0; i < q; i++)
out2[i] = out[i];
return out2;
}
/*
4 2 2
0 0 1
0 2 3
0 0
1 2
100 8 6
0 3 99
0 2 1
0 5 98
1 99 3
0 40 80
0 30 80
1 80 30
1 1 2
7 8
7 98
0 38
4 50
2 12
6 90
*/
Compilation message
collapse.cpp: In function 'void solve(int, int, int)':
collapse.cpp:95:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < oper[p].size(); i++){
~~^~~~~~~~~~~~~~~~
collapse.cpp:109:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < todo[l].size(); i++){
~~^~~~~~~~~~~~~~~~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:176:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < q; i++)
^~~
collapse.cpp:178:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
return out2;
^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
12544 KB |
Output is correct |
| 2 |
Execution timed out |
15010 ms |
12288 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
15340 KB |
Output is correct |
| 2 |
Execution timed out |
15073 ms |
15224 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
15212 KB |
Output is correct |
| 2 |
Execution timed out |
15089 ms |
15096 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
12544 KB |
Output is correct |
| 2 |
Execution timed out |
15010 ms |
12288 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
