#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=(_b); ++i)
#define FORR(i,a,b) for (int i=(a),_b=(b); i>=(_b); --i)
#define REP(i,b) for (int i=0,_b=(b); i<(_b); ++i)
#define endl '\n'
#define sz(x) (int) x.size()
#define mod %
#define fillchar(x,y,z) memset(x,z,y)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define sqr(x) ((x)*(x))
typedef long long int64;
typedef unsigned long long qword;
using namespace std;
const int base=10007;
const int maxn=1e5+5;
int st[maxn*4][21];
int a[maxn],b[maxn];
int n,C;
inline void Merge(int L[], int R[], int a[])
{
}
void build(int id, int l, int r)
{
if (l==r) {
st[id][0]=b[l];
st[id][1]=a[l];
return;
}
int mid=(l+r)>>1;
build(id<<1,l,mid); build(id<<1|1,mid+1,r);
FOR(x,0,C) st[id][x]=0;
FOR(x,0,C) FOR(y,0,C) {
int k=x+y;
if (k>=C) k=C;
st[id][k]+=st[id<<1][x]*st[id<<1|1][y];
if (st[id][k]>2e9) st[id][k]%=base;
}
FOR(x,0,C) if (st[id][x]>=base) st[id][x]%=base;
}
void update(int id, int l, int r, int u, int x, int y)
{
if (l>u||r<u) return;
if (l==r) {
st[id][0]=y;
st[id][1]=x;
return;
}
int mid=(l+r)>>1;
update(id<<1,l,mid,u,x,y); update(id<<1|1,mid+1,r,u,x,y);
FOR(x,0,C) st[id][x]=0;
FOR(x,0,C) FOR(y,0,C) {
int k=x+y;
if (k>=C) k=C;
st[id][k]+=st[id<<1][x]*st[id<<1|1][y];
if (st[id][k]>2e9) st[id][k]%=base;
}
FOR(x,0,C) if (st[id][x]>=base) st[id][x]%=base;
}
int main()
{
#ifdef meomeomeooooo
freopen("input.txt","r",stdin);
//freopen(".out","w",stdout);
#endif // meomeomeooooo
iostream::sync_with_stdio(false);
cin.tie(0);
cin >> n >> C;
FOR(i,1,n) cin >> a[i];
FOR(i,1,n) cin >> b[i];
FOR(i,1,n) a[i]%=base,b[i]%=base;
build(1,1,n);
int q;
cin >> q;
FOR(i,1,q) {
int id,x,y;
cin >> id >> x >> y;
x%=base; y%=base;
update(1,1,n,id,x,y);
cout << st[1][C] << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
560 KB |
Output is correct |
| 2 |
Correct |
9 ms |
512 KB |
Output is correct |
| 3 |
Correct |
22 ms |
512 KB |
Output is correct |
| 4 |
Correct |
340 ms |
11844 KB |
Output is correct |
| 5 |
Correct |
1131 ms |
23092 KB |
Output is correct |
| 6 |
Correct |
1558 ms |
22940 KB |
Output is correct |
| 7 |
Correct |
633 ms |
11972 KB |
Output is correct |
| 8 |
Correct |
405 ms |
22704 KB |
Output is correct |
| 9 |
Correct |
808 ms |
22992 KB |
Output is correct |
| 10 |
Correct |
2547 ms |
22944 KB |
Output is correct |
