#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define f first
#define s second
const int maxn = 1e5 + 5e4 + 10;
int n, m, a[maxn], b[maxn];
vector<int> sexo[maxn], q[maxn];
bool ans;
struct edge{
int l, r, u, v;
edge():l(0), r(0), u(0), v(0){}
edge(int l, int r, int u, int v):l(l), r(r), u(u), v(v){}
};
class DSU{
private:
int pai[maxn], sz[maxn];
bool ok[maxn];
stack<pii> s;
public:
void init(int n){ for(int i=1; i<=n; i++) pai[i] = i, sz[i] = 1; }
int find(int x){ return pai[x] == x ? x : find(pai[x]); }
void join(int a, int b){
a = find(a), b = find(b);
if(a == b){
s.push({0, 0});
return;
}
if(sz[a] > sz[b]) swap(a, b);
pai[a] = b;
sz[b] += sz[a];
s.push({a, b});
}
void rollback(){
int a = s.top().f, b = s.top().s;
s.pop();
pai[a] = a;
sz[b] -= sz[a];
}
void att(int x, bool v){ ok[find(x)] = v; }
bool query(int x){ return ok[find(x)]; }
}dsu;
class SEG{
private:
vector<pii> tree[1<<19];
public:
void build(int node, int tl, int tr){
tree[node].clear();
if(tl == tr) return;
int mid = (tl + tr) >> 1;
build(2*node, tl, mid); build(2*node+1, mid+1, tr);
}
void update(int node, int tl, int tr, edge e){
if(tl > e.r or tr < e.l) return;
if(tl >= e.l and tr <= e.r){
tree[node].push_back({e.u, e.v});
return;
}
int mid = (tl + tr) >> 1;
update(2*node, tl, mid, e); update(2*node+1, mid+1, tr, e);
}
void solve(int node, int tl, int tr){
for(pii p : tree[node]) dsu.join(p.f, p.s);
if(tl == tr){
for(int x : sexo[tl]) dsu.att(x, 1);
for(int x : q[tl]) ans &= dsu.query(x);
for(int x : sexo[tl]) dsu.att(x, 0);
}
else{
int mid = (tl + tr) >> 1;
solve(2*node, tl, mid); solve(2*node+1, mid+1, tr);
}
for(pii p : tree[node]) dsu.rollback();
}
}seg;
void reset(){
dsu.init(n);
seg.build(n);
for(int i=1; i<=n; i++) sexo[i].clear(), q[i].clear();
ans = 1;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin >> t;
while(t--){
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=n; i++) cin >> b[i];
reset();
for(int i=1; i<=n; i++){
if(a[i] < b[i]) ans = 0;
q[b[i]].push_back(i);
sexo[a[i]].push_back(i);
}
for(int i=1; i<=m; i++){
int u, v;
cin >> u >> v;
int r = min(a[u], a[v]), l = max(b[u], b[v]);
if(l > r) continue;
edge e(l, r, u, v);
seg.update(1, 1, n, e);
}
seg.solve(1, 1, n);
cout << ans << "\n";
}
return 0;
}
Compilation message
colors.cpp: In member function 'void SEG::solve(int, int, int)':
colors.cpp:77:11: warning: variable 'p' set but not used [-Wunused-but-set-variable]
77 | for(pii p : tree[node]) dsu.rollback();
| ^
colors.cpp: In function 'void reset()':
colors.cpp:83:13: error: no matching function for call to 'SEG::build(int&)'
83 | seg.build(n);
| ^
colors.cpp:51:7: note: candidate: 'void SEG::build(int, int, int)'
51 | void build(int node, int tl, int tr){
| ^~~~~
colors.cpp:51:7: note: candidate expects 3 arguments, 1 provided
