Submission #874947

#TimeUsernameProblemLanguageResultExecution timeMemory
874947serifefedartarRelativnost (COCI15_relativnost)C++17
0 / 140
2581 ms38304 KiB
#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[4*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 timeMemoryGrader output
Fetching results...