#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int mxN = 1e5 + 5;
ll n,C,c[mxN],c1[mxN],a[mxN],b[mxN],q,mod = 10007,ans;
struct segtree{
vector<vector<ll>> v;
vector<ll> v1;
ll sz = 1;
void init(){
while(sz < n) sz *= 2;
v.assign(2 * sz, vector<ll>(25));
v1.assign(2 * sz, 1LL);
for(int i = 0; i < 2 * sz; i++) v[i][0] = 1;
}
void set(ll i, ll x, ll l, ll r){
if(r - l == 1){
v[x][0] = b[i];
v[x][1] = a[i];
v1[x] = (a[i] + b[i]) % mod;
return;
}
ll mid = l + (r - l) / 2;
if(i < mid) set(i, 2 * x + 1, l, mid);
else set(i, 2 * x + 2, mid, r);
for(int j = 0; j < C; j++) v[x][j] = 0;
for(int j = 0; j < C; j++) for(int k = 0; k + j < C; k++)
v[x][k + j] = (v[x][j + k] + v[2 * x + 1][j] * v[2 * x + 2][k]) % mod;
v1[x] = v1[2 * x + 1] * v1[2 * x + 2] % mod;
}
void set(ll i){
set(i, 0, 0, sz);
}
// void find(ll l, ll r, ll x, ll lx, ll rx){
// if(lx >= r or rx <= l) return;
// if(lx >= l and rx <= r){
// for(int i = 0; i < C; i++){
// for(int j = 0; j + i < C; j++) c1[i + j] = (c1[i + j] + c[i] * v[x][j]) % mod;
// c[i] = c1[i];
// }
// ans *= v1[x];
// return;
// }
// ll mid = lx + (rx - lx) / 2;
// find(l, r, 2 * x + 1, lx, mid);
// find(l, r, 2 * x + 2, mid, rx);
// }
//
// void find(ll l, ll r){
// for(int i = 0; i < C; i++){
// c[i] = c1[i] = 0;
// }
// c[0] = 1;
// ans = 1;
// find(l, r, 0, 0, sz);
// }
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> C;
segtree s;
s.init();
for(int i = 0; i < n; i++){
cin >> a[i];
a[i] %= mod;
}
for(int i = 0; i < n; i++){
cin >> b[i];
b[i] %= mod;
s.set(i);
}
cin >> q;
while(q--){
ll i,a1,b1;
cin >> i >> a1 >> b1;
i--;
a[i] = a1 % mod;
b[i] = b1 % mod;
s.set(i);
ans = s.v1[0];
for(int i1 = 0; i1 < C; i1++){
ans = (ans - s.v[0][i1] + mod) % mod;
}
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2908 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2908 KB |
Output is correct |
| 3 |
Correct |
9 ms |
3000 KB |
Output is correct |
| 4 |
Runtime error |
205 ms |
33616 KB |
Memory limit exceeded |
| 5 |
Runtime error |
748 ms |
63572 KB |
Memory limit exceeded |
| 6 |
Runtime error |
1180 ms |
63528 KB |
Memory limit exceeded |
| 7 |
Correct |
463 ms |
32340 KB |
Output is correct |
| 8 |
Runtime error |
335 ms |
63572 KB |
Memory limit exceeded |
| 9 |
Runtime error |
441 ms |
63640 KB |
Memory limit exceeded |
| 10 |
Runtime error |
1493 ms |
64516 KB |
Memory limit exceeded |
