#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> p_sum(100005,0), w(100005,0);
const ll mod = 1e9+2022;
struct Node{
Node *l_child, *r_child;
int l,r, sum; bool lazy;
Node(){}
Node(int _l, int _r){
l = _l; r = _r; sum=0; lazy = false;
int m = (l+r)/2;
if(r-l > 1){
l_child = new Node(l,m);
r_child = new Node(m,r);
}
//cout << l << " " << r << "\n";
}
void push(){
if(!lazy) return;
if(r-l==1){
lazy = false;
sum = w[l] - sum;
}
else{
lazy = false;
if(l_child->lazy) l_child->push();
if(r_child->lazy) r_child->push();
l_child->lazy = true;
r_child->lazy = true;
sum = (p_sum[r] - p_sum[l] - sum + 2*mod);
while(sum >= mod) sum -= mod;
}
}
void flip(int L, int R){
push();
if(R <= l || L >= r) return; //not intersect
else if(L <= l && r <= R) lazy = true;
else if(r-l == 1){
sum = w[l] - sum;
}
else{
l_child->flip(L,R); r_child->flip(L,R);
l_child->push(); r_child->push();
sum = ((l_child->sum) + (r_child->sum));
while(sum >= mod) sum -= mod;
}
}
ll query(){
push(); return sum;
}
};
ll exp(ll a, ll n){
if(n==0) return 1;
if(n==1) return a%mod;
ll x = exp(a, n/2);
if(n%2==0) return (x*x)%mod;
else return (((x*x)%mod)*a)%mod;
}
const ll p = 2;
const ll q = 223;
const ll r = 2242157;
const ll phi = (p-1)*(q-1)*(r-1);
struct mint{
int vp, vq; ll n;
mint(ll _n){
vp = 0; vq = 0;
n = _n;
while(n%p==0){vp++; n/=p;}
while(n%q==0){vq++; n/=q;}
n = n%mod;
}
mint(int _vp, int _vq, ll _n){
vp = _vp; vq = _vq; n = _n%mod;
}
friend mint operator *(mint a, mint b){
return mint(a.vp+b.vp, a.vq+b.vq, a.n*b.n);
}
mint inv(){
return mint(-vp, -vq, exp(n,phi-1));
}
friend mint operator /(mint a, mint b){
return a * b.inv();
}
ll to_int(){
assert(vp >= 0 && vq >= 0);
ll m=n;
m = (m*exp(p,vp)) % mod;
m = (m*exp(q,vq)) % mod;
return m;
}
};
int n,m;
Node tr(0,100005);
void init(int _n, int _m, std::vector<int> p, std::vector<int> a){
n = _n; m = _m;
//step 1: compute degree
vector<int> adj[n];
vector<int> d(n,0);
vector<mint> d_mod(n,1);
mint prod(1);
for(int i=1; i<n+m; ++i){
adj[p[i]].push_back(i);
d[p[i]]++;
}
for(int i=0; i<n; ++i){
d_mod[i] = mint(d[i]);
prod = prod * d_mod[i];
}
//step 2: dfs to find weight of each leaf
vector<mint> node_w(n+m, mint(1));
node_w[0] = prod;
vector<int> st(1,0);
while(!st.empty()){
int v = st[st.size()-1];
st.pop_back();
//cout << v << "\n";
for(int u : adj[v]){
node_w[u] = node_w[v] / d_mod[v];
if(u < n) st.push_back(u);
}
}
//step 3: build the tree
p_sum[0] = 0;
for(int i=0; i<m; ++i){
w[i] = node_w[i+n].to_int();
p_sum[i+1] = (p_sum[i] + w[i]) % mod;
}
for(int i=0; i<m; ++i){
if(a[i] == 1) tr.flip(i,i+1);
}
}
int count_ways(int l, int r){
tr.flip(l-n,r-n+1);
return tr.query();
}
/*int main(){
for(int i=0; i<100; ++i){
w[i] = i;
p_sum[i+1] = p_sum[i] + w[i];
}
tr.flip(3,6);
cout << tr.query() << "\n";
tr.flip(5,10);
cout << tr.query() << "\n";
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
11216 KB |
Output is correct |
| 2 |
Correct |
11 ms |
11216 KB |
Output is correct |
| 3 |
Correct |
9 ms |
11336 KB |
Output is correct |
| 4 |
Correct |
9 ms |
11312 KB |
Output is correct |
| 5 |
Correct |
9 ms |
11308 KB |
Output is correct |
| 6 |
Correct |
10 ms |
11312 KB |
Output is correct |
| 7 |
Correct |
10 ms |
11216 KB |
Output is correct |
| 8 |
Correct |
9 ms |
11216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
11216 KB |
Output is correct |
| 2 |
Correct |
9 ms |
11268 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
11340 KB |
1st lines differ - on the 1st token, expected: '655368480', found: '360409272' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
11216 KB |
Output is correct |
| 2 |
Correct |
11 ms |
11216 KB |
Output is correct |
| 3 |
Correct |
9 ms |
11336 KB |
Output is correct |
| 4 |
Correct |
9 ms |
11312 KB |
Output is correct |
| 5 |
Correct |
9 ms |
11308 KB |
Output is correct |
| 6 |
Correct |
10 ms |
11312 KB |
Output is correct |
| 7 |
Correct |
10 ms |
11216 KB |
Output is correct |
| 8 |
Correct |
9 ms |
11216 KB |
Output is correct |
| 9 |
Correct |
9 ms |
11216 KB |
Output is correct |
| 10 |
Correct |
9 ms |
11268 KB |
Output is correct |
| 11 |
Incorrect |
9 ms |
11340 KB |
1st lines differ - on the 1st token, expected: '655368480', found: '360409272' |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
696 ms |
15496 KB |
Output is correct |
| 2 |
Correct |
1000 ms |
19732 KB |
Output is correct |
| 3 |
Correct |
1012 ms |
19728 KB |
Output is correct |
| 4 |
Correct |
873 ms |
19712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
696 ms |
15496 KB |
Output is correct |
| 2 |
Correct |
1000 ms |
19732 KB |
Output is correct |
| 3 |
Correct |
1012 ms |
19728 KB |
Output is correct |
| 4 |
Correct |
873 ms |
19712 KB |
Output is correct |
| 5 |
Execution timed out |
3030 ms |
15392 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
11216 KB |
Output is correct |
| 2 |
Correct |
9 ms |
11268 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
11340 KB |
1st lines differ - on the 1st token, expected: '655368480', found: '360409272' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
11216 KB |
Output is correct |
| 2 |
Correct |
11 ms |
11216 KB |
Output is correct |
| 3 |
Correct |
9 ms |
11336 KB |
Output is correct |
| 4 |
Correct |
9 ms |
11312 KB |
Output is correct |
| 5 |
Correct |
9 ms |
11308 KB |
Output is correct |
| 6 |
Correct |
10 ms |
11312 KB |
Output is correct |
| 7 |
Correct |
10 ms |
11216 KB |
Output is correct |
| 8 |
Correct |
9 ms |
11216 KB |
Output is correct |
| 9 |
Correct |
9 ms |
11216 KB |
Output is correct |
| 10 |
Correct |
9 ms |
11268 KB |
Output is correct |
| 11 |
Incorrect |
9 ms |
11340 KB |
1st lines differ - on the 1st token, expected: '655368480', found: '360409272' |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
11216 KB |
Output is correct |
| 2 |
Correct |
11 ms |
11216 KB |
Output is correct |
| 3 |
Correct |
9 ms |
11336 KB |
Output is correct |
| 4 |
Correct |
9 ms |
11312 KB |
Output is correct |
| 5 |
Correct |
9 ms |
11308 KB |
Output is correct |
| 6 |
Correct |
10 ms |
11312 KB |
Output is correct |
| 7 |
Correct |
10 ms |
11216 KB |
Output is correct |
| 8 |
Correct |
9 ms |
11216 KB |
Output is correct |
| 9 |
Correct |
9 ms |
11216 KB |
Output is correct |
| 10 |
Correct |
9 ms |
11268 KB |
Output is correct |
| 11 |
Incorrect |
9 ms |
11340 KB |
1st lines differ - on the 1st token, expected: '655368480', found: '360409272' |
| 12 |
Halted |
0 ms |
0 KB |
- |
