# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
93629 | dfistric | Relativnost (COCI15_relativnost) | C++14 | 4088 ms | 24192 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>
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;
const int OFF = (1 << 17);
const int MOD = 10007;
int tour[2 * OFF][22];
int A[OFF], B[OFF];
int C;
int add(int a, int b) {
return (a + b) % MOD;
}
int mul(int a, int b) {
return (a * b) % MOD;
}
void update(int x, int a, int b) {
x += OFF;
tour[x][0] = b % MOD;
tour[x][1] = a % MOD;
x /= 2;
while (x) {
REP(i, C + 1) tour[x][i] = 0;
REP(i, C + 1) {
REP(j, C + 1) {
int t = min(C, i + j);
tour[x][t] = add(tour[x][t], mul(tour[x * 2][i], tour[x * 2 + 1][j]));
}
}
x /= 2;
}
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, a, b, x;
cin >> n >> C;
REP(i, 2 * OFF) tour[i][0] = 1;
REP(i, n) cin >> A[i];
REP(i, n) cin >> B[i];
REP(i, n) {
update(i, A[i], B[i]);
}
int q;
cin >> q;
REP(i, q) {
cin >> x >> a >> b;
update(x - 1, a, b);
cout << tour[1][C] << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |