Submission #697279

#TimeUsernameProblemLanguageResultExecution timeMemory
697279kussssoRelativnost (COCI15_relativnost)C++17
0 / 140
1949 ms38216 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; const int N = 1e5 + 5; const int mod = 10007; int n, c; int q; int a[N]; int b[N]; struct Node { int tot; int dp[20]; Node() { for (int i = 0; i < 20; i++) dp[i] = 0; } } st[4 * N]; void update (int p, int va, int vb, int x = 1, int L = 1, int R = n) { if (L > p || R < p) return; if (L == R && R == p) { st[x].tot = (va + vb) % mod; st[x].dp[0] = vb; st[x].dp[1] = va; return; } int mid = (L + R) / 2; update(p, va, vb, x * 2, L, mid); update(p, va, vb, x * 2 + 1, mid + 1, R); st[x].tot = st[x * 2].tot * st[x * 2 + 1].tot % mod; for (int k = 0; k < c; k++) { st[x].dp[k] = 0; for (int i = 0; i <= k; i++) { st[x].dp[k] = (st[x].dp[k] + st[x * 2].dp[i] * st[x * 2 + 1].dp[k - i] % mod) % mod; } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> c; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> b[i]; for (int i = 1; i <= n; i++) update(i, a[i] % mod, b[i] % mod); cin >> q; while (q--) { int i, na, nb; cin >> i >> na >> nb; na %= mod; nb %= mod; update(i, na, nb); int total = st[1].tot; int bad = 0; // cout << '#' << st[1].dp[0] << '\n'; for (int k = 0; k < c; k++) bad = (bad + st[1].dp[k]) % mod; cout << (total + mod - bad) % mod << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...