Submission #98696

#TimeUsernameProblemLanguageResultExecution timeMemory
98696Dat160601Relativnost (COCI15_relativnost)C++17
0 / 140
4019 ms22640 KiB
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back #define fi first #define se second const int N = 1e5 + 7, mod = 10007; struct node{ int ret[21]; } it[4 * N]; int n, c, q, a, b, x; void add(int &a, int b){ b %= mod; a += b; if(a >= mod) a -= mod; } node merge(node a, node b){ node res; for(int i = 0; i <= c; i++) res.ret[i] = 0; for(int i = 0; i <= c; i++){ for(int j = 0; j <= c; j++){ add(res.ret[min(c, i + j)], a.ret[i] * b.ret[j]); } } return res; } void update(int k, int l, int r, int pos, int a, int b){ if(l > pos || r < pos) return; if(l == r){ it[k].ret[0] = b; it[k].ret[1] = a; return; } int mid = (l + r) >> 1; update(k << 1, l, mid, pos, a, b); update(k << 1 | 1, mid + 1, r, pos, a, b); it[k] = merge(it[k << 1], it[k << 1 | 1]); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> c; for(int i = 1; i <= n; i++){ cin >> a >> b; update(1, 1, n, i, a, b); } cin >> q; while(q --){ cin >> x >> a >> b; update(1, 1, n, x, a, b); cout << it[1].ret[c] << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...