Submission #98674

#TimeUsernameProblemLanguageResultExecution timeMemory
98674DrumpfTheGodEmperorRelativnost (COCI15_relativnost)C++14
140 / 140
1411 ms22140 KiB
#include <bits/stdc++.h> #define bp __builtin_popcountll #define pb push_back #define in(s) freopen(s, "r", stdin); #define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\ freopen((string(s) + "." + end2).c_str(), "w", stdout); #define fi first #define se second #define bw(i, r, l) for (int i = r - 1; i >= l; i--) #define fw(i, l, r) for (int i = l; i < r; i++) #define fa(i, x) for (auto i: x) using namespace std; const int mod = 1e4 + 7, inf = 1061109567; const long long infll = 4557430888798830399; const int N = 1e5 + 5; int n, c, a[N], b[N], sum = 0; void add(int &x, int y) { x += y; if (x >= mod) x -= mod; } int sadd(int x, int y) { add(x, y); return x; } int mul(int x, int y) { return 1ll * x * y % mod; } int ssub(int x, int y) { x -= y; if (x < 0) x += mod; return x; } int fpow(int a, int p) { if (!p) return 1; int tmp = fpow(a, p >> 1); tmp = mul(tmp, tmp); if (p & 1) tmp = mul(tmp, a); return tmp; } int inv(int a) { return fpow(a, mod - 2); } class SegmentTree { private: struct Node { int ans[20]; void init() { memset(ans, 0, sizeof ans); } Node operator+(const Node &rhs) const { Node res; res.init(); fw (i, 0, 20) { fw (j, 0, i + 1) add(res.ans[i], mul(ans[j], rhs.ans[i - j])); } return res; } } t[N << 2]; void build(int l, int r, int x) { if (l == r) { t[x].ans[0] = b[l]; t[x].ans[1] = a[l]; return; } int m = (l + r) >> 1; build(l, m, x << 1), build(m + 1, r, x << 1 | 1); t[x] = t[x << 1] + t[x << 1 | 1]; } void upd(int l, int r, int pos, int ap, int bp, int x) { if (l == r) { t[x].ans[0] = bp; t[x].ans[1] = ap; return; } int m = (l + r) >> 1; if (pos <= m) upd(l, m, pos, ap, bp, x << 1); else upd(m + 1, r, pos, ap, bp, x << 1 | 1); t[x] = t[x << 1] + t[x << 1 | 1]; } public: int n; void init(int _n) { n = _n; build(0, n - 1, 1); } void upd(int pos, int ap, int bp) { upd(0, n - 1, pos, ap, bp, 1); } int get() { int res = 0; fw (i, 0, c) add(res, t[1].ans[i]); return res; } } st; signed main() { #ifdef BLU in("blu.inp"); #endif ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> c; sum = 1; fw (i, 0, n) cin >> a[i], a[i] %= mod; fw (i, 0, n) cin >> b[i], b[i] %= mod; fw (i, 0, n) sum = mul(sum, sadd(a[i], b[i])); int q; cin >> q; st.init(n); while (q--) { int p, ap, bp; cin >> p >> ap >> bp; ap %= mod, bp %= mod; p--; sum = mul(sum, inv(sadd(a[p], b[p]))); a[p] = ap, b[p] = bp; sum = mul(sum, sadd(ap, bp)); st.upd(p, ap, bp); cout << ssub(sum, st.get()) << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...