#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
const int N = 1e5 + 5;
const int mod = 10007;
int n, c;
int q;
int a[N];
int b[N];
struct Node {
int tot;
int dp[20];
Node() {
for (int i = 0; i < 20; i++) dp[i] = 0;
}
}
st[4 * N];
void update (int p, int va, int vb, int x = 1, int L = 1, int R = n) {
if (L > p || R < p) return;
if (L == R && R == p) {
st[x].tot = (va + vb) % mod;
st[x].dp[0] = vb;
st[x].dp[1] = va;
return;
}
int mid = (L + R) / 2;
update(p, va, vb, x * 2, L, mid);
update(p, va, vb, x * 2 + 1, mid + 1, R);
st[x].tot = st[x * 2].tot * st[x * 2 + 1].tot % mod;
for (int k = 0; k < c; k++) {
st[x].dp[k] = 0;
for (int i = 0; i <= k; i++) {
st[x].dp[k] = (st[x].dp[k] + st[x * 2].dp[i] * st[x * 2 + 1].dp[k - i] % mod) % mod;
}
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> c;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
for (int i = 1; i <= n; i++) update(i, a[i] % mod, b[i] % mod);
cin >> q;
while (q--) {
int i, na, nb;
cin >> i >> na >> nb;
na %= mod;
nb %= mod;
update(i, na, nb);
int total = st[1].tot;
int bad = 0;
// cout << '#' << st[1].dp[0] << '\n';
for (int k = 0; k < c; k++) bad = (bad + st[1].dp[k]) % mod;
cout << (total + mod - bad) % mod << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
33236 KB |
Memory limit exceeded |
| 2 |
Runtime error |
19 ms |
33212 KB |
Memory limit exceeded |
| 3 |
Runtime error |
25 ms |
33236 KB |
Memory limit exceeded |
| 4 |
Runtime error |
252 ms |
34132 KB |
Memory limit exceeded |
| 5 |
Runtime error |
885 ms |
34592 KB |
Memory limit exceeded |
| 6 |
Runtime error |
1567 ms |
37724 KB |
Memory limit exceeded |
| 7 |
Runtime error |
575 ms |
34192 KB |
Memory limit exceeded |
| 8 |
Runtime error |
353 ms |
34204 KB |
Memory limit exceeded |
| 9 |
Runtime error |
497 ms |
34528 KB |
Memory limit exceeded |
| 10 |
Runtime error |
1949 ms |
38216 KB |
Memory limit exceeded |
