Submission #93631

#TimeUsernameProblemLanguageResultExecution timeMemory
93631dfistricRelativnost (COCI15_relativnost)C++14
42 / 140
3621 ms23576 KiB
#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, OFF) tour[i + OFF][0] = 1; REP(i, n) cin >> tour[i + OFF][1]; REP(i, n) cin >> tour[i + OFF][0]; FORd(x, OFF - 1, 1) { tour[x][0] = 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])); } } } 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 timeMemoryGrader output
Fetching results...