# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
874948 | serifefedartar | Relativnost (COCI15_relativnost) | C++17 | 2570 ms | 26348 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 <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 10007;
const ll LOGN = 20;
const ll MAXN = 1e5 + 100;
int A[MAXN], B[MAXN], C;
struct Node {
int taken[21];
Node() {
for (int i = 0; i < 21; i++)
taken[i] = 0;
}
};
Node sg[3*MAXN];
Node merge(Node a, Node b) {
Node new_node;
for (int i = 0; i <= C; i++) {
for (int j = 0; j <= C; j++)
new_node.taken[min(C, i + j)] = (new_node.taken[min(C, i + j)] + a.taken[i] * b.taken[j]) % MOD;
}
return new_node;
}
void init(int k, int a, int b) {
if (a == b) {
sg[k].taken[0] = B[a] % MOD;
sg[k].taken[1] = A[a] % MOD;
return ;
}
init(2*k, a, (a+b)/2);
init(2*k+1, (a+b)/2+1, b);
sg[k] = merge(sg[2*k], sg[2*k+1]);
}
void update(int k, int a, int b, int plc, pair<int,int> v) {
if (b < plc || a > plc)
return ;
if (a == b) {
sg[k].taken[0] = v.s % MOD;
sg[k].taken[1] = v.f % MOD;
return ;
}
update(2*k, a, (a+b)/2, plc, v);
update(2*k+1, (a+b)/2+1, b, plc, v);
sg[k] = merge(sg[2*k], sg[2*k+1]);
}
int main() {
fast
int N;
cin >> N >> C;
for (int i = 1; i <= N; i++)
cin >> A[i];
for (int i = 1; i <= N; i++)
cin >> B[i];
init(1, 1, N);
int Q, P, a, b;
cin >> Q;
while (Q--) {
cin >> P >> a >> b;
update(1, 1, N, P, {a, b});
cout << sg[1].taken[C] << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |