#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF (long long) 1e18//1234567890987654321
#define INF 1234567890
#define pb push_back
#define ins insert
#define f first
#define s second
#define db 0
#define EPS (1e-7) //0.0000001 the value
#define PI (acos(-1))
#define MAXN 300006
#define MAXK 26
#define MAXX 15000006
#define ll /*long long*/ int
#define ld long double
#define rep0(kk, l1, l2)for(ll kk = l1; kk < l2; kk++)
#define rep1(kk, l1, l2)for(ll kk = l1; kk <= l2; kk++)
#define foritr(itr, A) for(set<ll>::iterator itr = A.begin(); itr != A.end(); itr++)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ii++)
#define cr(x) cerr << #x << " = " << x << "\n";
#define crA(x, A) cerr << #x << " = " << A[x] << "\n";
#define spacing if(db)cout << " ";
#define space " "
#define cbr cout << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)));
#define bg(ms) (*ms.begin())
#define ed(ms) (*prev(ms.end(), 1))
#define addedge(a, b, c, v) v[(a)].pb(pi((b), (c))); v[(b)].pb(pi((a), (c)))
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n, c, A[MAXN/3], B[MAXN/3], q, C;
const long long MOD = (ll)10007;
struct node{
ll s, e, m, v, dpdp[25],c,I;
long long dp[25];
node *l, *r;
node(ll _s, ll _e)
{
s = _s, e = _e, m = (s+e)/2; c = min(e-s+1,C);
v = 0; I = 0;
mmst(dp,0);
if(s!=e)
{
l = new node(s,m);
r = new node(m+1,e);
}
if(s==e)
{
dp[0] = (B[s])%MOD;
dp[1] = A[s]%MOD;
return;
}
FOR(i,0,c)
{
dp[i] = 0;
for(ll j = 0; j <= i; j++)
{
dp[i] += ((l->dp[j] * r->dp[i-j])%MOD);
dp[i]%=MOD;
}
}
for(ll i = 0; i <= c; i++)
{
for(ll j = c-i; j <= c; j++)
{
dp[c] += ((l->dp[i] * r->dp[j])%MOD);
dp[c] %= MOD;
}
}
return;
}
void update(ll x)
{
if(s==e)
{
dp[0] = (B[s])%MOD;
dp[1] = A[s]%MOD;
return;
}
if(x>m) r->update(x);
else l->update(x);
mmst(dp,0);
FOR(i,0,c)
{
dp[i] = 0;
for(ll j = 0; j <= i; j++)
{
dp[i] += ((l->dp[j] * r->dp[i-j])%MOD);
dp[i]%=MOD;
}
}
for(ll i = 0; i <= c; i++)
{
for(ll j = c-i; j <= c; j++)
{
dp[c] += ((l->dp[i] * r->dp[j])%MOD);
dp[c] %= MOD;
}
}
assert(l->dp[c+1] == 0);
assert(r->dp[c+1] == 0);
// FOR(i,0,c+1)
// {
// FOR(j,0,c+1) if(i+j > c) I += ((l->dp[i] * r->dp[j])%MOD);
// }
return;
}
ll sz()
{
return e-s+1;
}
void trace()
{
if(s==e) { cout << s << ": " << dp[0] << ' ' << dp[1] << '\n'; return; }
l->trace();
r->trace();
cout << s << ' ' << m << ' ' << e << ' ' << dp[0] << ' ' << dp[1] << ' ' << dp[2] << ' ' << dp[3] << '\n';
}
} *seg;
int main()
{
FAST
cin >> n >> c; C=c;
FOR(i,0,n) cin >> A[i];
FOR(i,0,n) cin >> B[i];
seg = new node(0, n-1);
cin >> q;
FOR(ii,0,q)
{
ll x, a, b;
cin >> x >> a >> b; --x;
A[x]=a,B[x]=b;
seg->update(x);
cout << seg->dp[c] << "\n";
// seg->trace();
}
}
/*
4 2
1 2 3 4
1 2 3 4
1
4 1 1
* */
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
11 ms |
888 KB |
Output is correct |
| 3 |
Correct |
18 ms |
888 KB |
Output is correct |
| 4 |
Runtime error |
51 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
64 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
71 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
58 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
65 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
61 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
66 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
