#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
const int N=200050;
const int L=19;
struct DSU
{
int p[N];
void init(){ for(int i=0;i<N;i++) p[i]=i;}
DSU(){ init();}
int Find(int x){ return p[x]==x?x:p[x]=Find(p[x]);}
void Union(int x, int y){ p[Find(x)]=Find(y);}
} DS;
struct BIT
{
int sum[N];
void init(){ for(int i=0;i<N;i++) sum[i]=0;}
BIT(){ init();}
void Add(int i, int f){ for(;i<N;i+=i&-i) sum[i]+=f;}
int Get(int i){ int ret=0;for(;i;i-=i&-i) ret+=sum[i];return ret;}
int Get(int l, int r){ return Get(r)-Get(l-1);}
} BT;
struct Tree
{
vector<int> E[N];
int par[N][L],dep[N],root,nod[N],lid[N],rid[N],tid;
Tree(){}
void AddEdge(int u, int v){ E[u].pb(v);E[v].pb(u);}
void SetRoot(int u){ root=u;}
void DFS(int u, int p)
{
lid[u]=++tid;
nod[tid]=u;
par[u][0]=p;
dep[u]=dep[p]+1;
//printf("%i ",u);
for(int i=1;i<L;i++) par[u][i]=par[par[u][i-1]][i-1];
for(int v:E[u]) if(v!=p) DFS(v,u);
//printf("%i ",u);
rid[u]=tid;
}
void DFS(){ DFS(root,0);}//printf("\n");}
int UpLo(int u, int x)
{
for(int i=L-1;~i;i--) if(par[u][i]!=0 && par[u][i]<=x) u=par[u][i];
return u;
}
int UpHi(int u, int x)
{
for(int i=L-1;~i;i--) if(par[u][i]!=0 && par[u][i]>=x) u=par[u][i];
return u;
}
} Lree,Rree;
struct Query
{
int l,r,mul,id;
Query(int b=0, int c=0, int e=0, int f=0){ l=b,r=c,mul=e,id=f;}
};
int sol[N];
struct QuerySolver
{
int a[N],b[N],id[N],n;
vector<Query> Qs[N];
QuerySolver(){}
void init(int v[], int u[], int sz)
{
n=sz;
for(int i=1;i<=n;i++) a[i]=v[i],b[i]=u[i];
for(int i=1;i<=n;i++) id[b[i]]=i;
}
void AddQuery(int s, int e, int l, int r, int idex)
{
Qs[s-1].pb(Query(l,r,-1,idex));
Qs[e].pb(Query(l,r,1,idex));
}
void Solve()
{
for(int i=1;i<=n;i++)
{
BT.Add(id[a[i]],1);
for(Query my:Qs[i])
{
sol[my.id]+=my.mul*BT.Get(my.l,my.r);
}
}
}
} Solver;
vector<int> E[N];
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(),q=s.size();
for(int i=0;i<m;i++) x[i]++,y[i]++;
for(int i=0;i<q;i++) s[i]++,e[i]++,l[i]++,r[i]++;
for(int i=0;i<m;i++) x[i]++,y[i]++;
for(int i=0;i<q;i++) s[i]++,e[i]++,l[i]++,r[i]++;
n+=2;
for(int i=2;i<=n;i++) E[1].pb(i);
for(int i=1;i<n;i++) E[n].pb(i);
for(int i=0;i<m;i++) E[x[i]].pb(y[i]),E[y[i]].pb(x[i]);
DS.init();
for(int i=1;i<=n;i++) for(int j:E[i]) if(j<i && DS.Find(i)!=DS.Find(j)) Lree.AddEdge(DS.Find(j),i),DS.Union(j,i);
DS.init();
for(int i=n;i>=1;i--) for(int j:E[i]) if(j>i && DS.Find(i)!=DS.Find(j)) Rree.AddEdge(DS.Find(j),i),DS.Union(j,i);
Lree.SetRoot(n);Rree.SetRoot(1);
Lree.DFS();Rree.DFS();
//for(int i=1;i<=n;i++) printf("%i ",Lree.nod[i]);printf("\n");
//for(int i=1;i<=n;i++) printf("%i ",Rree.nod[i]);printf("\n");
BT.init();
Solver.init(Lree.nod,Rree.nod,n);
for(int i=0;i<q;i++)
{
int u=Rree.UpHi(s[i],l[i]);
int v=Lree.UpLo(e[i],r[i]);
Solver.AddQuery(Lree.lid[v],Lree.rid[v],Rree.lid[u],Rree.rid[u],i);
}
vector<int> ret;
Solver.Solve();
for(int i=0;i<q;i++) ret.pb(sol[i]>0);
return ret;
}
/*int read_int(){ int x;scanf("%i",&x);return x;}
int main() {
int N = read_int();
int M = read_int();
int Q = read_int();
std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
for (int j = 0; j < M; ++j) {
X[j] = read_int();
Y[j] = read_int();
}
for (int i = 0; i < Q; ++i) {
S[i] = read_int();
E[i] = read_int();
L[i] = read_int();
R[i] = read_int();
}
std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
for (size_t i = 0; i < A.size(); ++i) {
printf("%d\n", A[i]);
}
return 0;
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
20736 KB |
Output is correct |
2 |
Correct |
19 ms |
20736 KB |
Output is correct |
3 |
Correct |
20 ms |
20736 KB |
Output is correct |
4 |
Correct |
18 ms |
20736 KB |
Output is correct |
5 |
Correct |
18 ms |
20736 KB |
Output is correct |
6 |
Correct |
19 ms |
20732 KB |
Output is correct |
7 |
Correct |
20 ms |
20736 KB |
Output is correct |
8 |
Correct |
27 ms |
20808 KB |
Output is correct |
9 |
Correct |
19 ms |
20736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
20736 KB |
Output is correct |
2 |
Correct |
19 ms |
20736 KB |
Output is correct |
3 |
Correct |
20 ms |
20736 KB |
Output is correct |
4 |
Correct |
18 ms |
20736 KB |
Output is correct |
5 |
Correct |
18 ms |
20736 KB |
Output is correct |
6 |
Correct |
19 ms |
20732 KB |
Output is correct |
7 |
Correct |
20 ms |
20736 KB |
Output is correct |
8 |
Correct |
27 ms |
20808 KB |
Output is correct |
9 |
Correct |
19 ms |
20736 KB |
Output is correct |
10 |
Correct |
27 ms |
22088 KB |
Output is correct |
11 |
Correct |
26 ms |
22108 KB |
Output is correct |
12 |
Correct |
27 ms |
22080 KB |
Output is correct |
13 |
Correct |
26 ms |
22128 KB |
Output is correct |
14 |
Correct |
26 ms |
22108 KB |
Output is correct |
15 |
Correct |
27 ms |
22116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
947 ms |
109220 KB |
Output is correct |
2 |
Correct |
1044 ms |
111624 KB |
Output is correct |
3 |
Correct |
929 ms |
109916 KB |
Output is correct |
4 |
Correct |
812 ms |
108928 KB |
Output is correct |
5 |
Correct |
822 ms |
108592 KB |
Output is correct |
6 |
Correct |
898 ms |
108824 KB |
Output is correct |
7 |
Correct |
823 ms |
107840 KB |
Output is correct |
8 |
Correct |
848 ms |
111760 KB |
Output is correct |
9 |
Correct |
664 ms |
109764 KB |
Output is correct |
10 |
Correct |
593 ms |
107980 KB |
Output is correct |
11 |
Correct |
603 ms |
108524 KB |
Output is correct |
12 |
Correct |
693 ms |
108356 KB |
Output is correct |
13 |
Correct |
1004 ms |
111560 KB |
Output is correct |
14 |
Correct |
965 ms |
111392 KB |
Output is correct |
15 |
Correct |
967 ms |
111380 KB |
Output is correct |
16 |
Correct |
949 ms |
111436 KB |
Output is correct |
17 |
Correct |
839 ms |
108268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
20736 KB |
Output is correct |
2 |
Correct |
19 ms |
20736 KB |
Output is correct |
3 |
Correct |
20 ms |
20736 KB |
Output is correct |
4 |
Correct |
18 ms |
20736 KB |
Output is correct |
5 |
Correct |
18 ms |
20736 KB |
Output is correct |
6 |
Correct |
19 ms |
20732 KB |
Output is correct |
7 |
Correct |
20 ms |
20736 KB |
Output is correct |
8 |
Correct |
27 ms |
20808 KB |
Output is correct |
9 |
Correct |
19 ms |
20736 KB |
Output is correct |
10 |
Correct |
27 ms |
22088 KB |
Output is correct |
11 |
Correct |
26 ms |
22108 KB |
Output is correct |
12 |
Correct |
27 ms |
22080 KB |
Output is correct |
13 |
Correct |
26 ms |
22128 KB |
Output is correct |
14 |
Correct |
26 ms |
22108 KB |
Output is correct |
15 |
Correct |
27 ms |
22116 KB |
Output is correct |
16 |
Correct |
947 ms |
109220 KB |
Output is correct |
17 |
Correct |
1044 ms |
111624 KB |
Output is correct |
18 |
Correct |
929 ms |
109916 KB |
Output is correct |
19 |
Correct |
812 ms |
108928 KB |
Output is correct |
20 |
Correct |
822 ms |
108592 KB |
Output is correct |
21 |
Correct |
898 ms |
108824 KB |
Output is correct |
22 |
Correct |
823 ms |
107840 KB |
Output is correct |
23 |
Correct |
848 ms |
111760 KB |
Output is correct |
24 |
Correct |
664 ms |
109764 KB |
Output is correct |
25 |
Correct |
593 ms |
107980 KB |
Output is correct |
26 |
Correct |
603 ms |
108524 KB |
Output is correct |
27 |
Correct |
693 ms |
108356 KB |
Output is correct |
28 |
Correct |
1004 ms |
111560 KB |
Output is correct |
29 |
Correct |
965 ms |
111392 KB |
Output is correct |
30 |
Correct |
967 ms |
111380 KB |
Output is correct |
31 |
Correct |
949 ms |
111436 KB |
Output is correct |
32 |
Correct |
839 ms |
108268 KB |
Output is correct |
33 |
Correct |
1110 ms |
110344 KB |
Output is correct |
34 |
Correct |
380 ms |
61384 KB |
Output is correct |
35 |
Correct |
1111 ms |
112380 KB |
Output is correct |
36 |
Correct |
1000 ms |
109804 KB |
Output is correct |
37 |
Correct |
1377 ms |
111876 KB |
Output is correct |
38 |
Correct |
1055 ms |
110308 KB |
Output is correct |
39 |
Correct |
945 ms |
115480 KB |
Output is correct |
40 |
Correct |
1131 ms |
116332 KB |
Output is correct |
41 |
Correct |
860 ms |
109904 KB |
Output is correct |
42 |
Correct |
759 ms |
108372 KB |
Output is correct |
43 |
Correct |
1147 ms |
115784 KB |
Output is correct |
44 |
Correct |
914 ms |
111340 KB |
Output is correct |
45 |
Correct |
797 ms |
116060 KB |
Output is correct |
46 |
Correct |
811 ms |
115676 KB |
Output is correct |
47 |
Correct |
979 ms |
111696 KB |
Output is correct |
48 |
Correct |
945 ms |
111564 KB |
Output is correct |
49 |
Correct |
978 ms |
111796 KB |
Output is correct |
50 |
Correct |
978 ms |
111552 KB |
Output is correct |
51 |
Correct |
1054 ms |
117336 KB |
Output is correct |
52 |
Correct |
1047 ms |
117480 KB |
Output is correct |