#include <bits/stdc++.h>
using namespace std;
#define ll long long
constexpr ll MOD = 1000002022;
constexpr int MAXN = 2e5 + 5;
vector<int> adj[MAXN];
pair<ll, ll> dp[MAXN]; // attivo, spento
int N, M;
vector<int> A;
vector<int> P;
int PW;
vector<ll> mult(vector<ll> &a, vector<ll> &b) { // b size è il minore ed è sempre 2
int dim = (a.size() - 1) + (b.size() - 1) + 1;
vector<ll> res(dim);
for (int i = 0; i < a.size(); i ++) {
for (int j = 0; j < b.size(); j ++) {
int sum = (i + j < dim) ? i + j : i + j - dim;
res[sum] += (a[i] * b[j]) % MOD;
res[sum] %= MOD;
}
}
return res;
}
pair<ll, ll> merge(int a, int b) {
vector<ll> poly_a = {dp[a].second, dp[a].first};
vector<ll> poly_b = {dp[b].second, dp[b].first};
vector<ll> poly = mult(poly_a, poly_b);
ll acceso = 0;
ll spento = 0;
for (int i = 0; i < poly.size(); i ++) {
acceso += (poly[i] * i) % MOD;
acceso %= MOD;
spento += (poly[i] * (poly.size() - 1 - i)) % MOD;
spento %= MOD;
}
return {acceso, spento};
}
void init(int N, int M, vector<int> P, vector<int> A) {
:: N = N;
:: M = M;
:: A = A;
:: P = P;
:: PW = M;
for (int i = 1; i < N + M; i ++) {
adj[P[i]].push_back(i);
}
// dp 1 based
for (int i = 0; i < PW; i ++) dp[PW + i] = {A[i], A[i] ^ 1};
for (int i = PW - 1; i >= 1; i --) dp[i] = merge(2 * i, 2 * i + 1);
// for (int i = 1; i < 2 * PW; i ++) {
// cout << "seg i : " << i << " -> " << dp[i].first << " " << dp[i].second << '\n';
// }
}
void update(int idx, int l, int r, int ql, int qr) {
// cout << "idx, l, r, ql, qr : " << idx << " " << l << " " << r << " " << ql << " " << qr << '\n';
if (ql <= l && r <= qr) {
auto [acceso, spento] = dp[idx];
dp[idx] = {spento, acceso};
return;
}
if (r <= ql || qr <= l) return;
update(2 * idx , (l + r) / 2, r, ql, qr);
update(2 * idx + 1, l, (l + r) / 2, ql, qr);
dp[idx] = merge(2 * idx, 2 * idx + 1);
}
int count_ways(int L, int R) {
update(1, 0, PW, L - N, R + 1 - N);
return dp[1].first;
}
Compilation message
circuit.cpp: In function 'std::vector<long long int> mult(std::vector<long long int>&, std::vector<long long int>&)':
circuit.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (int i = 0; i < a.size(); i ++) {
| ~~^~~~~~~~~~
circuit.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for (int j = 0; j < b.size(); j ++) {
| ~~^~~~~~~~~~
circuit.cpp: In function 'std::pair<long long int, long long int> merge(int, int)':
circuit.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i = 0; i < poly.size(); i ++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4952 KB |
1st lines differ - on the 1st token, expected: '509', found: '760936692' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4952 KB |
3rd lines differ - on the 1st token, expected: '585825652', found: '518438250' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4952 KB |
1st lines differ - on the 1st token, expected: '509', found: '760936692' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
554 ms |
8280 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '357186114' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
554 ms |
8280 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '357186114' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4952 KB |
3rd lines differ - on the 1st token, expected: '585825652', found: '518438250' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4952 KB |
1st lines differ - on the 1st token, expected: '509', found: '760936692' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4952 KB |
1st lines differ - on the 1st token, expected: '509', found: '760936692' |
| 4 |
Halted |
0 ms |
0 KB |
- |
