# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
306214 | fishy15 | Relativnost (COCI15_relativnost) | C++14 | 50 ms | 65540 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 10007
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
// change if necessary
#define MAXN 1000000
using namespace std;
int n, c, q;
ll a[MAXN];
ll b[MAXN];
struct node {
ll nums[21];
node() { memset(nums, 0, sizeof nums); nums[0] = 1; }
node(ll a, ll b) {
memset(nums, 0, sizeof nums);
nums[0] = b % MOD;
nums[1] = a % MOD;
}
node operator*(const node &b) {
node ans;
ans.nums[0] = 0;
for (int i = 0; i <= c; i++) {
for (int j = 0; j <= c; j++) {
int p = min(i + j, c);
ans.nums[p] += nums[i] * b.nums[j] % MOD;
if (ans.nums[p] >= MOD) ans.nums[p] -= MOD;
}
}
return ans;
}
};
node st[4 * MAXN];
void build(int v, int l, int r) {
if (l == r) {
st[v] = node(a[l], b[r]);
} else {
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
st[v] = st[2 * v] * st[2 * v + 1];
}
}
void upd(int v, int l, int r, int x, int a, int b) {
if (l == r) {
st[v] = node(a, b);
::a[x] = a;
::b[x] = b;
} else {
int m = (l + r) / 2;
if (x <= m) {
upd(2 * v, l, m, x, a, b);
} else {
upd(2 * v + 1, m + 1, r, x, a, b);
}
st[v] = st[2 * v] * st[2 * v + 1];
}
}
node qry(int v, int l, int r, int x, int y) {
if (x <= l && r <= y) {
return st[v];
} else if (r < x || l > y) {
return node();
} else {
int m = (l + r) / 2;
return qry(2 * v, l, m, x, y) * qry(2 * v + 1, m + 1, r, x, y);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> c;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
build(1, 0, n - 1);
cin >> q;
while (q--) {
int p, a, b; cin >> p >> a >> b;
p--;
upd(1, 0, n - 1, p, a, b);
cout << qry(1, 0, n - 1, 0, n - 1).nums[c] << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |