#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, k, m, c, q;
vector <short int> a, b;
struct Node
{
vector <short int> f;
unsigned short int l, r;
} T[maxn * 4];
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)
{
res.f[min (c, i + j)] += L.f[i] * R.f[j];
}
}
void Build (int id)
{
int l = T[id].l, r = T[id].r, mid = (l + r) >> 1;
T[id].f.resize (c + 1, 0);
if (l == r)
{
T[id].f[0] = b[l];
T[id].f[1] = a[l];
return;
}
T[id<<1].l = l, T[id<<1].r = mid;
T[id<<1|1].l = mid+1, T[id<<1|1].r = r;
Build (id<<1);
Build (id<<1|1);
Merge (T[id], T[id<<1], T[id<<1|1]);
}
int pos;
void Update (int id)
{
int l = T[id].l, r = T[id].r;
if (l > pos or pos > r) return;
if (l == r)
{
T[id].f[0] = b[l];
T[id].f[1] = a[l];
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 >> a[i];
for (int i = 1; i <= n; ++i)
cin >> b[i];
cin >> q;
}
void Solve ()
{
T[1].l = 1, T[1].r = n;
Build (1);
for (;q;--q)
{
cin >> pos;
cin >> a[pos] >> b[pos];
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 |
Incorrect |
6 ms |
14680 KB |
Output isn't correct |
| 2 |
Incorrect |
9 ms |
14680 KB |
Output isn't correct |
| 3 |
Incorrect |
16 ms |
14680 KB |
Output isn't correct |
| 4 |
Incorrect |
29 ms |
18116 KB |
Output isn't correct |
| 5 |
Incorrect |
16 ms |
16864 KB |
Output isn't correct |
| 6 |
Incorrect |
33 ms |
17416 KB |
Output isn't correct |
| 7 |
Incorrect |
43 ms |
20776 KB |
Output isn't correct |
| 8 |
Incorrect |
16 ms |
16624 KB |
Output isn't correct |
| 9 |
Incorrect |
6 ms |
15504 KB |
Output isn't correct |
| 10 |
Incorrect |
6 ms |
15488 KB |
Output isn't correct |
