#include "werewolf.h"
# include <bits/stdc++.h>
using namespace std;
const int maxn = 400010;
const int MAXN = 400005;
const int logN = 20;
struct DSU
{
int par[MAXN];
DSU()
{
int i;
for(i=0;i<maxn;i++)
{
par[i] = i;
}
}
int root(int v)
{
if(par[v]==v)return v;
par[v] = root(par[v]);
return par[v];
}
void connect(int v, int u)
{
int v1 = root(v);
int u1 = root(u);
par[v1] = u1;
}
};
struct Task
{
int x, y1,y2,type,idx;
Task(int __x, int __y)
{
x = __x;
y1 = __y;
type = 2;
}
Task(int __x, int __y1, int __y2, int __type, int __idx)
{
x = __x;
y1 = __y1;
y2 = __y2;
type = __type;
idx = __idx;
}
};
vector <Task> q;
DSU du,dv;
vector <int> U[MAXN], V[MAXN];
vector <int> g[MAXN];
vector <int> eV,eU;
int inV[MAXN],outV[MAXN],inU[MAXN],outU[MAXN];
int upV[MAXN][21],upU[MAXN][21];
int pU[MAXN];
void dfsV(int v, int p)
{
//cout<<v<<endl;
eV.push_back(v);
inV[v] = eV.size()-1;
upV[v][0] = p;
for(auto u:V[v])
{
if(u==p)continue;
dfsV(u,v);
}
outV[v] = eV.size()-1;
return ;
}
void dfsU(int v, int p)
{
// cout<<v<<endl;
eU.push_back(v);
inU[v] = eU.size()-1;
upU[v][0] = p;
for(auto u:U[v])
{
if(u==p)continue;
dfsU(u,v);
}
outU[v] = eU.size()-1;
return ;
}
bool cmp(Task i, Task j)
{
if(i.x==j.x)
{
if(i.type == 2)return true;
if(j.type == 2)return false;
return i.type<j.type;
}
return i.x<j.x;
}
struct Fenwik
{
int fen[maxn];
void update(int idx, int delta)
{
idx++;
for(;idx<maxn;idx+= (idx&(-idx)))
{
fen[idx]+=delta;
}
}
int query(int idx)
{
idx++;
int ans = 0;
for(;idx>0;idx-=(idx&(-idx)))
{
ans+=fen[idx];
}
return ans;
}
int diff(int a, int b)
{
// a++;
// b++;
if(a==0)
return query(b);
int ans = query(b)-query(a-1);
// cout<<"DIFF"<<a<<" "<<b<<" "<<ans<<endl;
return ans;
}
};
Fenwik f;
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int i,j;
for(i=0;i<X.size();i++)
{
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for(i=0;i<N;i++)
{
for(auto v:g[i])
{
//cout<<v<<endl;
if(v>=i)continue;
int u1 = dv.root(i);
int v1 = dv.root(v);
if(u1==v1)continue;
V[u1].push_back(v1);
V[v1].push_back(u1);
dv.connect(v1,u1);
}
}
dfsV(N-1,N-1);
for(i=N-1;i>=0;i--)
{
for(auto v:g[i])
{
if(v<=i)continue;
int u1 = du.root(i);
int v1 = du.root(v);
if(u1==v1)continue;
U[u1].push_back(v1);
U[v1].push_back(u1);
// cout<<"Edge "<<u1<<" "<<v1<<endl;
du.connect(v1,u1);
}
}
dfsU(0,0);
/* for(i=0;i<N;i++)
cout<<eU[i]<<" ";
cout<<endl;
for(i=0;i<N;i++)
cout<<i<<" : "<<inU[i]<<" "<<outU[i]<<endl;*/
for(i=1;i<logN;i++)
{
for(j=0;j<N;j++)
{
upV[j][i] = upV[upV[j][i-1]][i-1];
upU[j][i] = upU[upU[j][i-1]][i-1];
}
}
for(i=0;i<N;i++)
{//cout<<eU[i]<<" "<<i<<endl;
pU[eU[i]] = i;
}
for(i=0;i<N;i++)
{
// cout<<i<<" & "<<pU[eV[i]]<<endl;
q.push_back(Task(i,pU[eV[i]]));
}
for(i=0;i<S.size();i++)
{
int s = S[i];
int e = E[i];
int l = L[i];
int r = R[i];
for(j = logN-1;j>=0;j--)
{
if(upV[e][j]<=r)
{
e = upV[e][j];
}
if(upU[s][j]>=l)
{
s = upU[s][j];
}
}
int l1 = inV[e];
int r1 = outV[e];
int l2 = inU[s];
int r2 = outU[s];
// cout<<i<<" : "<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<endl;
q.push_back(Task(l1-1,l2,r2,0,i));
q.push_back(Task(r1,l2,r2,1,i));
}
sort(q.begin(),q.end(),cmp);
std::vector<int> A(S.size());
for(i=0;i<q.size();i++)
{
Task cur = q[i];
// cout<<cur.x<<" "<<cur.type<<endl;
if(cur.type==2)
{
// cout<<"ADD "<<cur.y1<<endl;
f.update(cur.y1,1);
}
if(cur.type==0)
{
//cout<<cur.idx<<"|| "<<cur.x<<" "<<cur.type<<" "<<cur.y1<<" "<<cur.y2<<" "<<f.diff(cur.y1,cur.y2)<<endl;
A[cur.idx]-=f.diff(cur.y1,cur.y2);
}
if(cur.type==1)
{//cout<<cur.idx<<"&& "<<cur.x<<" "<<cur.type<<" "<<cur.y1<<" "<<cur.y2<<" "<<f.diff(cur.y1,cur.y2)<<endl;
A[cur.idx]+=f.diff(cur.y1,cur.y2);
}
}
for(i=0;i<S.size();i++)
{
if(A[i]>0)A[i] = 1;
else
A[i] = 0;
if(S[i]<L[i]||E[i]>R[i])
A[i] = 0;
// cout<<A[i]<<" ";
} //cout<<endl;
return A;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
Compilation message
werewolf.cpp: In member function 'int Fenwik::diff(int, int)':
werewolf.cpp:122:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
122 | if(a==0)
| ^~
werewolf.cpp:124:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
124 | int ans = query(b)-query(a-1);
| ^~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:136:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for(i=0;i<X.size();i++)
| ~^~~~~~~~~
werewolf.cpp:196:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for(i=0;i<S.size();i++)
| ~^~~~~~~~~
werewolf.cpp:223:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Task>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
223 | for(i=0;i<q.size();i++)
| ~^~~~~~~~~
werewolf.cpp:242:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
242 | for(i=0;i<S.size();i++)
| ~^~~~~~~~~
werewolf.cpp:245:7: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
245 | else
| ^~~~
werewolf.cpp:247:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
247 | if(S[i]<L[i]||E[i]>R[i])
| ^~
werewolf.cpp: In function 'void __static_initialization_and_destruction_0(int, int)':
werewolf.cpp:16:20: warning: iteration 400005 invokes undefined behavior [-Waggressive-loop-optimizations]
16 | par[i] = i;
| ~~~~~~~^~~
werewolf.cpp:14:18: note: within this loop
14 | for(i=0;i<maxn;i++)
| ~^~~~~
werewolf.cpp:16:20: warning: iteration 400005 invokes undefined behavior [-Waggressive-loop-optimizations]
16 | par[i] = i;
| ~~~~~~~^~~
werewolf.cpp:14:18: note: within this loop
14 | for(i=0;i<maxn;i++)
| ~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
67 ms |
63980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
67 ms |
63980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
541 ms |
159200 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
67 ms |
63980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
