#include "circuit.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll MOD=1'000'002'022;
inline ll safe_mod(ll x,ll p) {
x%=p;
if(x<0)x+=p;
return x;
}
template<typename T,auto op,auto e,typename F,auto mapp,auto comp,auto id>
struct LST {
vector<T> value;
vector<F> delay;
int size;
explicit LST(int sz):value(sz*2,e()),delay(sz,id()),size(sz){}
inline T _get(const int pos) {
return mapp(delay[pos],value[pos]);
}
void _delay(const int pos) {
int k=0;
int p=pos;
while(p>1) {
k++;
p/=2;
}
for(int i=k; i>=1; i--) {
p=pos>>i;
value[p]=_get(p);
delay[p*2]=comp(delay[p],delay[p*2]);
delay[p*2+1]=comp(delay[p],delay[p*2+1]);
delay[p]=id();
}
}
void _calc(int pos) {
pos/=2;
while(pos>=1) {
value[pos]=op(_get(pos*2),_get(pos*2+1));
pos/=2;
}
}
T get(const int pos) {
return _get(pos+size);
}
void set(const int pos,const T val) {
_delay(pos+size);
value[pos+size]=val;
delay[pos+size]=id();
_calc(pos+size);
}
T prod(int lf,int ri) {
lf+=size;
ri+=size;
_delay(lf);
_delay(ri-1);
T ret_lf=e(),ret_ri=e();
while(lf<ri) {
if(lf&1) {
ret_lf=op(ret_lf,_get(lf));
lf++;
}
if(ri&1) {
ri--;
ret_ri=op(_get(ri),ret_ri);
}
lf/=2;
ri/=2;
}
return op(ret_lf,ret_ri);
}
void apply(int lf,int ri,F f) {
lf+=size;
ri+=size;
int update_lf=lf;
int update_ri=ri-1;
_delay(update_lf);
_delay(update_ri);
while(lf<ri) {
if(lf&1) {
delay[lf]=comp(f,delay[lf]);
lf++;
}
if(ri&1) {
ri--;
delay[ri]=comp(f,delay[ri]);
}
lf/=2;
ri/=2;
}
_calc(update_lf);
_calc(update_ri);
}
};
template<typename T,auto op,auto e>
struct SegTree {
vector<T> value;
int size;
explicit SegTree(int sz):value(sz*2,e()),size(sz){}
inline T _get(const int pos) {
return value[pos];
}
void _calc(int pos) {
pos/=2;
while(pos>=1) {
value[pos]=op(_get(pos*2),_get(pos*2+1));
pos/=2;
}
}
T get(const int pos) {
return _get(pos+size);
}
void set(const int pos,const T val) {
value[pos+size]=val;
_calc(pos+size);
}
T prod(int lf,int ri) {
lf+=size;
ri+=size;
T ret_lf=e(),ret_ri=e();
while(lf<ri) {
if(lf&1) {
ret_lf=op(ret_lf,_get(lf));
lf++;
}
if(ri&1) {
ri--;
ret_ri=op(_get(ri),ret_ri);
}
lf/=2;
ri/=2;
}
return op(ret_lf,ret_ri);
}
};
ll prod_op(const ll x,const ll y) {
return safe_mod(x*y,MOD);
}
ll prod_e() {
return 1;
}
pair<ll,ll> op(const pair<ll,ll> x,const pair<ll,ll> y) {
return {safe_mod(x.first+y.first,MOD),safe_mod(x.second+y.second,MOD)};
}
pair<ll,ll> e() {
return {0,0};
}
pair<ll,ll> mapp(const bool f,const pair<ll,ll> x) {
if(f)return {safe_mod(x.second-x.first,MOD),x.second};
return x;
}
bool comp(const bool f,const bool g) {
return f!=g;
}
bool id() {
return false;
}
SegTree<ll,prod_op,prod_e> init_seg(0);
LST<pair<ll,ll>,op,e,bool,mapp,comp,id> seg(0);
vector<vector<int>> tree;
int n,m;
void dfs(int pos) {
if(n<=pos) {
seg.set(pos-n,{0,init_seg.prod(0,n)});
}
else {
init_seg.set(pos,1);
for(int i:tree[pos]) {
dfs(i);
}
init_seg.set(pos,tree[pos].size());
}
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n=N;
m=M;
tree.resize(N+M);
init_seg=SegTree<ll,prod_op,prod_e>(N);
seg=LST<pair<ll,ll>,op,e,bool,mapp,comp,id>(M);
rng(i,1,N+M) {
tree[P[i]].emplace_back(i);
}
rep(i,N) {
init_seg.set(i,tree[i].size());
}
dfs(0);
rep(i,M) {
if(A[i]==1)seg.apply(i,i+1,true);
}
}
int count_ways(int L, int R) {
seg.apply(L-n,R+1-n,true);
return seg.prod(0,m).first;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3136 ms |
1913316 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3136 ms |
1913316 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
