#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
long long n,m;
vector<long long> p2(300001);
vector<long long> haha[300001];
vector<long long> st(300001);
vector<long long> wow(300001);
vector<long long> no(300001);
vector<long long> sum(800001);
vector<long long> idk(800001);
vector<long long> val(800001);
const long long MOD = 1e9+2022;
void build(long long l, long long r, long long x) {
if(l == r) {
sum[x] = wow[l+n];
if(no[l]) {
val[x] = sum[l];
}
else {
val[x] = 0;
}
idk[x] = 0;
return;
}
long long mid = (l+r)/2;
build(l,mid,x*2+1);
build(mid+1,r,x*2+2);
sum[x] = (sum[x*2+1]+sum[x*2+2])%MOD;
val[x] = (val[x*2+1]+val[x*2+2])%MOD;
}
void upd(long long l, long long r, long long ql, long long qr, long long x) {
if(l == ql && r == qr) {
idk[x]++;
idk[x]%=2;
val[x] = (sum[x]-val[x]+MOD)%MOD;
return;
}
long long mid = (l+r)/2;
if(qr <= mid) {
upd(l,mid,ql,qr,x*2+1);
}
else if(ql >= mid+1) {
upd(mid+1,r,ql,qr,x*2+2);
}
else {
upd(l,mid,ql,mid,x*2+1);
upd(mid+1,r,mid+1,qr,x*2+2);
}
val[x] = (val[x*2+1]+val[x*2+2])%MOD;
if(idk[x]%2) {
val[x] = (sum[x]-val[x]+MOD)%MOD;
}
}
void dfs(long long a) {
long long sb = 0;
if(a < n) {
sb = 1;
}
for(long long v: haha[a]) {
dfs(v);
sb+=st[v];
}
st[a] = sb;
}
void dude(long long a) {
if(!haha[a].empty()) {
wow[haha[a][0]] = wow[a]+st[haha[a][1]];
wow[haha[a][1]] = wow[a]+st[haha[a][0]];
dude(haha[a][0]);
dude(haha[a][1]);
}
}
void init(int N, int M, vector<int> p, vector<int> a) {
n = N;
m = M;
p2[0] = 1;
for(long long i = 1; i < 300000; i++) {
p2[i] = (p2[i-1]*2)%MOD;
}
for(long long i = 1; i < n+m; i++) {
haha[p[i]].push_back(i);
}
dfs(0);
dude(0);
for(int i = n; i < n+m; i++) {
wow[i] = p2[wow[i]];
}
for(int i = 0; i < a.size(); i++) {
no[i] = a[i];
}
build(0,m-1,0);
}
int count_ways(int l, int r) {
upd(0,m-1,l-n,r-n,0);
return val[0];
}
Compilation message
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
35536 KB |
Output is correct |
| 2 |
Execution timed out |
3068 ms |
35516 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
35536 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
35536 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '767326892' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
35536 KB |
Output is correct |
| 2 |
Execution timed out |
3068 ms |
35516 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
387 ms |
37340 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '475683344' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
387 ms |
37340 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '475683344' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
35536 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
35536 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '767326892' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
35536 KB |
Output is correct |
| 2 |
Execution timed out |
3068 ms |
35516 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
35536 KB |
Output is correct |
| 2 |
Execution timed out |
3068 ms |
35516 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
