#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
#define whole(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define sqr(x) ((x)*(x))
#define pb push_back
#define mp make_pair
#define ins insert
#define maxn int (1e5 + 1)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
//----------------------------------------------------------
int n, x, y, c, q, mod = 1e4 + 7;
vector <short int> a, b;
struct Node
{
vector <short int> f;
unsigned short int l, r;
} T[maxn];
void Merge (Node &res, Node L, Node R)
{
fill (whole (res.f), 0);
for (int i = 0; i <= c; ++i)
for (int j = 0; j <= c; ++j)
{
int x = min (c, i + j);
res.f[x] = (res.f[x] + L.f[i] * R.f[j]) % mod;
}
}
void Build (int id)
{
T[id].f.resize (c + 1, 0);
if (T[id].l == T[id].r)
{
T[id].f[0] = b[T[id].l];
T[id].f[1] = a[T[id].l];
return;
}
T[id<<1].l = T[id].l, T[id<<1].r = (T[id].l + T[id].r) >> 1;
T[id<<1|1].l = ((T[id].l + T[id].r) >> 1) + 1, T[id<<1|1].r = T[id].r;
Build (id<<1);
Build (id<<1|1);
Merge (T[id], T[id<<1], T[id<<1|1]);
}
int pos;
void Update (int id)
{
if (T[id].l > pos or pos > T[id].r) return;
if (T[id].l == T[id].r)
{
T[id].f[0] = b[pos];
T[id].f[1] = a[pos];
return;
}
Update (id<<1);
Update (id<<1|1);
Merge (T[id], T[id<<1], T[id<<1|1]);
}
void Input ()
{
cin >> n >> c;
a.resize (n + 1);
b.resize (n + 1);
for (int i = 1; i <= n; ++i)
cin >> x, a[i] = x % mod;
for (int i = 1; i <= n; ++i)
cin >> x, b[i] = x % mod;
cin >> q;
}
void Solve ()
{
T[1].l = 1, T[1].r = n;
Build (1);
for (;q;--q)
{
cin >> pos >> x >> y;
a[pos] = x % mod, b[pos] = y % mod;
Update (1);
cout << T[1].f[c] << '\n';
}
}
int main()
{
//freopen ("relativnost.inp", "r", stdin);
//freopen ("relativnost.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie (NULL);
cout.tie (NULL);
Input ();
Solve ();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
5304 KB |
Output is correct |
| 2 |
Correct |
26 ms |
5304 KB |
Output is correct |
| 3 |
Correct |
49 ms |
5304 KB |
Output is correct |
| 4 |
Runtime error |
33 ms |
7156 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
69 ms |
7488 KB |
Execution killed because of forbidden syscall writev (20) |
| 6 |
Runtime error |
129 ms |
8040 KB |
Execution killed because of forbidden syscall writev (20) |
| 7 |
Runtime error |
79 ms |
8628 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
56 ms |
7248 KB |
Execution killed because of forbidden syscall writev (20) |
| 9 |
Runtime error |
33 ms |
6128 KB |
Execution killed because of forbidden syscall writev (20) |
| 10 |
Runtime error |
46 ms |
6112 KB |
Execution killed because of forbidden syscall writev (20) |
