#include "werewolf.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define erase_uni(x) x.erase(unique(all(x)),x.end())
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
/*using namespace __gnu_pbds;
template <class T> using oset = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using omset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;*/
//Note to self: Check for overflow
vector<vector<int>> manji(200005),veci(200005);
int up[200005];
vector<int> redosled[200005];
int poc[200005],kraj[200005];
int gde[200005];
int Up(int x)
{
if (up[x]<0) return x;
return up[x]=Up(up[x]);
}
void dsu(int a, int b)
{
a=Up(a),b=Up(b);
if (a==b) return;
if (up[a]<up[b]) swap(a,b);
up[b]+=up[a],up[a]=b;
for (auto it : redosled[a]) redosled[b].pb(it);
}
vector<pii> pom[200005];
int niz1[200005];
int l1[200005],r1[200005];
int niz2[200005];
int l2[200005],r2[200005];
int gdeu1[200005];
int k=1;
vector<int> val[550001];
int l[550001],r[550001];
int Qry(int p, int ll, int rr, int x)
{
if (ll>r[p] || rr<l[p]) return 0;
if (ll<=l[p] && rr>=r[p]) return lower_bound(all(val[p]),x)-val[p].begin();
return Qry(2*p,ll,rr,x)+Qry(2*p+1,ll,rr,x);
}
void ispisi()
{
for (int kk=1;kk<=k;kk*=2)
{
ff(i,kk,2*kk)
{
for (auto it : val[i]) cout<<it<<" ";
cout<<"; ";
} cout<<endl;
} cout<<endl;
}
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=X.size();
int q=S.size();
vector<int> ans(q,0);
ff(i,0,m)
{
if (X[i]>Y[i]) swap(X[i],Y[i]);
manji[Y[i]].pb(X[i]),veci[X[i]].pb(Y[i]);
}
///wolf form
ff(i,0,q) pom[i].clear();
ff(i,0,q) pom[R[i]].pb({E[i],i});
ff(i,0,n) up[i]=-1,redosled[i].clear(),redosled[i].pb(i);
ff(i,0,n)
{
for (auto it : manji[i]) dsu(i,it);
for (auto it : pom[i])
{
poc[it.yy]=redosled[Up(it.xx)].front();
kraj[it.yy]=redosled[Up(it.xx)].back();
}
}
ff(i,0,n) niz1[i]=redosled[Up(0)][i];
ff(i,0,n) gde[niz1[i]]=i;
ff(i,0,q) l1[i]=gde[poc[i]],r1[i]=gde[kraj[i]];
//ff(i,0,n) cout<<niz1[i]<<" "; cout<<endl;
//ff(i,0,q) cout<<"["<<l1[i]<<","<<r1[i]<<"]"<<endl; cout<<endl;
///human form
ff(i,0,q) pom[i].clear();
ff(i,0,q) pom[L[i]].pb({S[i],i});
ff(i,0,n) up[i]=-1,redosled[i].clear(),redosled[i].pb(i);
bff(i,0,n)
{
for (auto it : veci[i]) dsu(i,it);
for (auto it : pom[i])
{
poc[it.yy]=redosled[Up(it.xx)].front();
kraj[it.yy]=redosled[Up(it.xx)].back();
}
}
ff(i,0,n) niz2[i]=redosled[Up(0)][i];
ff(i,0,n) gde[niz2[i]]=i;
ff(i,0,q) l2[i]=gde[poc[i]],r2[i]=gde[kraj[i]];
//ff(i,0,n) cout<<niz2[i]<<" "; cout<<endl;
//ff(i,0,q) cout<<"["<<l2[i]<<","<<r2[i]<<"]"<<endl; cout<<endl;
///intersect?
ff(i,0,n) gdeu1[niz1[i]]=i;
while (k<n) k*=2;
ff(i,0,k) l[i+k]=i,r[i+k]=i;
bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
ff(i,0,n) val[i+k].pb(gdeu1[niz2[i]]);
bff(i,0,k) val[i].resize(val[2*i].size()+val[2*i+1].size()),merge(all(val[2*i]),all(val[2*i+1]),val[i].begin());
ff(i,0,q)
{
if (Qry(1,l2[i],r2[i],r1[i]+1)!=Qry(1,l2[i],r2[i],l1[i])) ans[i]=1;
}
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
0 3
2 5
4 2 1 2
4 2 2 2
5 4 3 4
6 6 21
5 1
1 2
1 3
3 4
0 3
2 5
0 0 0 0
0 0 1 1
0 0 2 2
0 0 3 3
0 0 4 4
0 0 5 5
1 1 1 1
1 1 2 2
1 1 3 3
1 1 4 4
1 1 5 5
2 2 2 2
2 2 3 3
2 2 4 4
2 2 5 5
3 3 3 3
3 3 4 4
3 3 5 5
4 4 4 4
4 4 5 5
5 5 5 5
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
64816 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
64816 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
666 ms |
209072 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
64816 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
