#include "circuit.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int N=1e5+500;
const ll mod=1000002022;
ll Puta(ll a,ll b){a%=mod,b%=mod;ll x=a*b;x%=mod;return x;}
ll Plus(ll a,ll b){a%=mod,b%=mod;ll x=a+b;x%=mod;return x;}
vector<int>E[2*N+500];
int a[N+500],n,m,P[2*N+500];
ll res[2*N+500],dp[2*N+500][2],F[N+500];
/*void DFSsetup(int u){
F[u]=E[u].size()+1;
for(auto i:E[u]){
DFSsetup(i);
F[u]*=F[i];
}
}*/
void DFS(int u){
if(E[u].empty()) return;
for(auto i:E[u]) DFS(i);
dp[u][1]=dp[u][0]=0;
int mask=0;
while(mask< (1<<(E[u].size()))){
ll temp1=1,sum=0;
for(int i=0,temp=mask;i<E[u].size();i++,temp/=2){
temp1=Puta(temp1,dp[E[u][i]][temp%2]);sum+=temp%2;
}
if(mask!=0) dp[u][1]=Plus(dp[u][1],Puta(sum,temp1));
dp[u][0]=Plus(dp[u][0],Puta(E[u].size()-sum,temp1));
mask++;
}
//dp[u][0]=F[u]-dp[u][1];
}
void Update1(int v){
dp[v][1]=1-dp[v][1];
dp[v][0]=1-dp[v][0];
int u=P[v];
while(u!=-1){
dp[u][1]=dp[u][0]=0;
int mask=0;
while(mask< (1<<(E[u].size()))){
ll temp1=1,sum=0;
for(int i=0,temp=mask;i<E[u].size();i++,temp/=2){
temp1=Puta(temp1,dp[E[u][i]][temp%2]);sum+=temp%2;
}
if(mask!=0) dp[u][1]=Plus(dp[u][1],Puta(sum,temp1));
dp[u][0]=Plus(dp[u][0],Puta(E[u].size()-sum,temp1));
mask++;
}
u=P[u];
}
}
int root,nc,sum[2*N],lc[2*N],rc[2*N],lazy[2*N];
void update(int c,int ss,int se,int qval){
if(qval==1) sum[c]=se-ss+1-sum[c];
lazy[c]+=qval;lazy[c]%=2;
}
void push(int c,int ss,int se){
int mid=(ss+se)/2;
update(lc[c],ss,mid,lazy[c]);
update(rc[c],mid+1,se,lazy[c]);
lazy[c]=0;
}
void Update(int &c,int ss,int se,int qs,int qe){
if(!c) c=++nc;
if(qs<=ss && se<=qe){
update(c,ss,se,1);
return;
}
if(qe<ss || se<qs) return;
int mid=(ss+se)/2;
push(c,ss,se);
Update(lc[c],ss,mid,qs,qe);
Update(rc[c],mid+1,se,qs,qe);
sum[c]=sum[lc[c]]+sum[rc[c]];
}
int Get(int c,int ss,int se,int qs,int qe){
if(qs<=ss && se<=qe) return sum[c];
if(qe<ss || se<qs) return 0;
int mid=(ss+se)/2;
push(c,ss,se);
return Get(lc[c],ss,mid,qs,qe)+Get(rc[c],mid+1,se,qs,qe);
}
void init(int N1, int M1, std::vector<int> P1, std::vector<int> A) {
n=N1,m=M1;
for(int i=0;i<P1.size();i++) P[i]=P1[i];
for(int i=0;i<P1.size();i++){
E[P[i]].pb(i);
}
for(int i=0;i<m;i++){
dp[n+i][1]=A[i],dp[n+i][0]=1-A[i];
a[i]=A[i];
if(A[i]==1) Update(root,0,m-1,i,i);
}
//DFSsetup(0);
for(int i=0;i<m;i++) dp[n+i][1]=0,dp[n+i][0]=1;
DFS(0);
/*for(int i=0;i<=n+m-1;i++){
printf("%i: %i %i\n",i,dp[i][0],dp[i][1]);
}*/
res[0]=dp[0][1];//printf("%i ",res[0]);
for(int i=0;i<m;i++){
Update1(n+i);
res[i+1]=dp[0][1];
//printf("%i ",res[i+1]);
}
//printf("\n");
}
int count_ways(int L, int R) {
if(n==1){
int ct=0;
for(int i=L;i<=R;i++) a[i-1]=1-a[i-1];
for(int i=0;i<=m-1;i++) ct+=a[i];
return ct;
}
if(n<=1000 || L==R) {
for(int i=L;i<=R;i++){
Update1(i);
}
return dp[0][1];
}
Update(root,0,m-1,L-n,R-n);
return res[Get(root,0,m-1,0,m-1)];
//DFS(0);
/*for(int i=0;i<=n+m-1;i++){
printf("%i: %i %i\n",i,dp[i][0],dp[i][1]);
}*/
}
Compilation message
circuit.cpp: In function 'void DFS(int)':
circuit.cpp:30:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i=0,temp=mask;i<E[u].size();i++,temp/=2){
| ~^~~~~~~~~~~~
circuit.cpp: In function 'void Update1(int)':
circuit.cpp:48:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i=0,temp=mask;i<E[u].size();i++,temp/=2){
| ~^~~~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:92:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i=0;i<P1.size();i++) P[i]=P1[i];
| ~^~~~~~~~~~
circuit.cpp:93:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i=0;i<P1.size();i++){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10592 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10828 KB |
Output is correct |
| 3 |
Execution timed out |
3055 ms |
10584 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
10584 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '259697650' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10592 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10828 KB |
Output is correct |
| 3 |
Execution timed out |
3055 ms |
10584 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
517 ms |
13692 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '480177418' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
517 ms |
13692 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '480177418' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
10584 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '259697650' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10592 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10828 KB |
Output is correct |
| 3 |
Execution timed out |
3055 ms |
10584 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10592 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10828 KB |
Output is correct |
| 3 |
Execution timed out |
3055 ms |
10584 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
