#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;
void Merge(int L[], int R[], int a[])
{
FOR(x,0,C) a[x]=0;
FOR(x,0,C) FOR(y,0,C) {
a[min(x+y,C)]+=L[x]*R[y];
if (a[min(x+y,C)]>2e9) a[min(x+y,C)]%=base;
}
FOR(x,0,C) a[x]%=base;
}
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);
Merge(st[id<<1],st[id<<1|1],st[id]);
}
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);
Merge(st[id<<1],st[id<<1|1],st[id]);
}
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 |
512 KB |
Output is correct |
2 |
Correct |
15 ms |
640 KB |
Output is correct |
3 |
Correct |
20 ms |
512 KB |
Output is correct |
4 |
Correct |
368 ms |
12004 KB |
Output is correct |
5 |
Correct |
1085 ms |
23152 KB |
Output is correct |
6 |
Correct |
1546 ms |
22956 KB |
Output is correct |
7 |
Correct |
693 ms |
12076 KB |
Output is correct |
8 |
Correct |
500 ms |
22920 KB |
Output is correct |
9 |
Correct |
680 ms |
22964 KB |
Output is correct |
10 |
Correct |
2467 ms |
23192 KB |
Output is correct |