//#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 2e5 + 100, M = 1e7 + 10;
vector <pair <int, int>> edge[N], inc[N], dcs[N], edge2[N];
int idl[N], idr[N], l1[N], r1[N], l2[N], r2[N];
struct node{
int s = 0;
int lson, rson;
node() {};
};
node seg[M];
int cnt = 1, root[N];
void build(int id, int l, int r) {
if (l == r) {
return;
}
int m = (l + r) / 2;
seg[id].lson = cnt++;
seg[id].rson = cnt++;
build(seg[id].lson, l, m);
build(seg[id].rson, m + 1, r);
}
void upd(int pid, int id, int l, int r, int v) {
if (l > v || r < v)
return;
if (l == r) {
return;
}
int m = (l + r) / 2;
if (v <= m) {
seg[id].rson = seg[pid].rson;
seg[id].lson = cnt;
seg[cnt].s = seg[seg[pid].lson].s + 1;
cnt++;
upd(seg[pid].lson, seg[id].lson, l, m, v);
} else {
seg[id].lson = seg[pid].lson;
seg[id].rson = cnt;
seg[cnt].s = seg[seg[pid].rson].s + 1;
cnt++;
upd(seg[pid].rson, seg[id].rson, m + 1, r, v);
}
}
ll get(int id, int l, int r, int u, int v) {
if (l > v || r < u)
return 0;
if (l >= u && r <= v) {
return seg[id].s;
}
int m = (l + r) / 2;
return get(seg[id].lson, l, m, u, v) + get(seg[id].rson, m + 1, r, u, v);
}
int pos[N];
vector <int> solve(vector <int> &p, vector <int> &q, int num) {
int n = sz(q) - 1;
for (int i = 1; i <= n; i++)
pos[p[i]] = i;
build(0, 1, n);
root[0] = 0;
for (int i = 1; i <= n; i++) {
//cout << q[i] << " ";
int x = q[i];
cnt++;
root[i] = cnt - 1;
seg[root[i]].s = seg[root[i - 1]].s + 1;
upd(root[i - 1], root[i], 1, n, pos[x]);
}
//cout << '\n';
vector <int> save;
for (int i = 0; i < num; i++) {
int v = get(root[r2[i]], 1, n, l1[i], r1[i]) - get(root[l2[i] - 1], 1, n, l1[i], r1[i]);
if (v) {
save.pb(1);
} else {
save.pb(0);
}
}
return save;
}
struct kruskal_tree{
int n;
vector <int> par, arr, in, ou;
vector < vector <int>> ed;
void dfs(int u) {
bool is = 0;
in[u] = sz(arr);
for (auto x : ed[u]) {
dfs(x);
is = 1;
}
if (is == 0) {
arr.pb(u);
}
ou[u] = sz(arr) - 1;
}
void assign(int N) {
arr.pb(0);
n = N;
par.assign(2 * n + 10, 0);
in.assign(2 * n + 10, 0);
ou.assign(2 * n + 10, 0);
ed.resize(2 * n + 10);
for (int i = 1; i <= n * 2; i++)
par[i] = i;
}
int find(int u) {
return par[u] == u ? u : find(par[u]);
}
void unite(int a, int b) {
a = find(a), b = find(b);
if (a == b)
return;
n++;
par[a] = par[b] = par[n] = n;
ed[n].pb(a);
ed[n].pb(b);
}
};
vector <int> check_validity(int N, vector <int>& x, vector <int>& y, vector <int>& s, vector <int>& e, vector <int>& l, vector <int>& r) {
int m = sz(x);
int n = N;
for (int i = 0; i < m; i++) {
x[i]++, y[i]++;
edge[max(x[i], y[i])].pb({x[i], y[i]});
edge2[min(x[i], y[i])].pb({x[i], y[i]});
}
kruskal_tree A, B;
A.assign(n);
B.assign(n);
int q = sz(s);
for (int i = 0; i < q; i++) {
l[i]++;
r[i]++;
s[i]++;
e[i]++;
inc[r[i]].pb({e[i], i});
dcs[l[i]].pb({s[i], i});
}
for (int i = 1; i <= n; i++) {
for (auto x : edge[i]) {
A.unite(x.f, x.s);
}
for (auto x : inc[i]) {
idl[x.s] = A.find(x.f);
}
}
for (int i = n; i >= 1; i--) {
for (auto x : edge2[i]) {
B.unite(x.f, x.s);
}
for (auto x : dcs[i]) {
idr[x.s] = B.find(x.f);
}
}
A.dfs(A.n);
B.dfs(B.n);
for (int i = 0; i < q; i++) {
l1[i] = A.in[idl[i]];
r1[i] = A.ou[idl[i]];
l2[i] = B.in[idr[i]];
r2[i] = B.ou[idr[i]];
//cout << l1[i] << ' ' << r1[i] << ' ' << l2[i] << ' ' << r2[i] << '\n';
}
return solve(A.arr, B.arr, q);
}
Compilation message
/usr/bin/ld: /tmp/cc81fO3U.o: in function `main':
grader.cpp:(.text.startup+0x377): undefined reference to `check_validity(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
