Submission #734038

#TimeUsernameProblemLanguageResultExecution timeMemory
734038GrindMachineRelativnost (COCI15_relativnost)C++17
140 / 140
1397 ms16228 KiB
// Om Namah Shivaya #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x, y) ((x + y - 1) / (y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i, n) for(int i = 0; i < n; ++i) #define rep1(i, n) for(int i = 1; i <= n; ++i) #define rev(i, s, e) for(int i = s; i >= e; --i) #define trav(i, a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a, b); } template<typename T> void amax(T &a, T b) { a = max(a, b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* */ const int MOD = 1e4 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; const int K = 20; template<typename T> struct segtree1 { // https://codeforces.com/blog/entry/18051 /*=======================================================*/ struct data { int a[K]; data() { memset(a, 0, sizeof a); a[0] = 1; } }; data neutral = data(); data merge(data &left, data &right) { data curr; memset(curr.a, 0, sizeof curr.a); rep(i, K) { rep(j, K - i) { curr.a[i + j] = (curr.a[i + j] + left.a[i] * right.a[j]) % MOD; } } return curr; } void create(int i, T v) { auto [x, y] = v; tr[i].a[0] = y % MOD; tr[i].a[1] = x % MOD; } void modify(int i, T v) { auto [x, y] = v; tr[i].a[0] = y % MOD; tr[i].a[1] = x % MOD; } /*=======================================================*/ int n; vector<data> tr; segtree1() { } segtree1(int siz) { init(siz); } void init(int siz) { n = siz; tr.assign(2 * n, neutral); } void build(vector<T> &a, int siz) { rep(i, siz) create(i + n, a[i]); rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]); } void pupd(int i, T v) { modify(i + n, v); for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]); } data query(int l, int r) { data resl = neutral, resr = neutral; for (l += n, r += n; l <= r; l >>= 1, r >>= 1) { if (l & 1) resl = merge(resl, tr[l++]); if (!(r & 1)) resr = merge(tr[r--], resr); } return merge(resl, resr); } }; template<typename T> struct segtree2 { // https://codeforces.com/blog/entry/18051 /*=======================================================*/ struct data { int a; }; data neutral = {1}; data merge(data &left, data &right) { data curr; curr.a = left.a * right.a % MOD; return curr; } void create(int i, T v) { tr[i].a = (v.ff + v.ss) % MOD; } void modify(int i, T v) { tr[i].a = (v.ff + v.ss) % MOD; } /*=======================================================*/ int n; vector<data> tr; segtree2() { } segtree2(int siz) { init(siz); } void init(int siz) { n = siz; tr.assign(2 * n, neutral); } void build(vector<T> &a, int siz) { rep(i, siz) create(i + n, a[i]); rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]); } void pupd(int i, T v) { modify(i + n, v); for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]); } data query(int l, int r) { data resl = neutral, resr = neutral; for (l += n, r += n; l <= r; l >>= 1, r >>= 1) { if (l & 1) resl = merge(resl, tr[l++]); if (!(r & 1)) resr = merge(tr[r--], resr); } return merge(resl, resr); } }; void solve(int test_case) { int n, k; cin >> n >> k; vector<pii> a(n + 5); rep1(i, n) cin >> a[i].ff; rep1(i, n) cin >> a[i].ss; segtree1<pii> st1(n + 5); st1.build(a, n + 1); segtree2<pii> st2(n + 5); st2.build(a, n + 1); int q; cin >> q; while (q--) { int i, x, y; cin >> i >> x >> y; st1.pupd(i, {x, y}); st2.pupd(i, {x, y}); auto res = st1.query(1, n); int ans = st2.query(1, n).a; rep(j, k) { ans = (ans - res.a[j] + MOD) % MOD; } cout << ans << endl; } } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...