#pragma GCC optimize ("Ofast")
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
#define int long long int
#define pb push_back
#define fi first
#define se second
#define deb cerr << "Line no." << __LINE__
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define IO ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define sz(x) (int)x.size()
const int mod = 10007;
const int mod1 = 998244353;
typedef double f80;
#ifndef LOCAL
#define endl '\n'
#endif
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
int pwr(int a,int b){
int ans = 1;
while(b){
if(b & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
const int N = 1e5 + 5;
vector<int> tr[4 * N];
int a[N], b[N], n, m;
vector<int> mul(vector<int> a,vector<int> b){
vector<int> c(sz(a) + sz(b), 0);
fr(i, 0, sz(a) - 1){
fr(j, 0, sz(b) - 1){
c[i + j] += (a[i] * b[j]) % mod;
if(c[i + j] >= mod) c[i + j] -= mod;
}
}
c.resize(m, 0);
return c;
}
void upd(int nd,int s,int e,int idx,int a,int b){
if(s == e){
tr[nd] = {b, a};
return;
}
int m = (s + e) >> 1;
if(idx <= m)
upd(nd << 1, s, m, idx, a, b);
else
upd(nd << 1 | 1, m + 1, e, idx, a, b);
tr[nd] = mul(tr[nd << 1], tr[nd << 1 | 1]);
}
vector<int> query(int nd,int s,int e,int l,int r){
if(s > r || e < l) return {0};
if(l <= s && e <= r) return tr[nd];
int m = (s + e) >> 1;
return mul(query(nd << 1, s, m, l, r), query(nd << 1 | 1, m + 1, e, l, r));
}
void solve(){
cin >> n >> m;
fr(i, 1, n){
cin >> a[i];
a[i] %= mod;
}
int tot = 1;
fr(i, 1, n){
cin >> b[i];
b[i] %= mod;
tot = (tot * (a[i] + b[i])) % mod;
upd(1, 1, n, i, a[i], b[i]);
}
int q;
cin >> q;
fr(i, 1, q){
int idx, aa, bb;
cin >> idx >> aa >> bb;
aa %= mod, bb %= mod;
tot = (tot * pwr(a[idx] + b[idx], mod - 2)) % mod;
a[idx] = aa, b[idx] = bb;
tot = (tot * (a[idx] + b[idx])) % mod;
upd(1, 1, n, idx, aa, bb);
int ans = tot;
vector<int> lol = query(1, 1, n, 1, n);
fr(i, 0, m - 1){
ans -= lol[i];
if(ans < 0) ans += mod;
}
cout << ans << endl;
}
}
signed main(){
IO;
#ifdef LOCAL
freopen("inp.txt","r", stdin);
// freopen("out.txt", "w", stdout);
#endif
clock_t clk = clock();
int t = 1;
// cin >> t;
fr(tt, 1, t){
solve();
}
//cerr << endl << (double)(clock() - clk) / CLOCKS_PER_SEC;
return 0;
}
Compilation message
relativnost.cpp: In function 'int main()':
relativnost.cpp:112:10: warning: unused variable 'clk' [-Wunused-variable]
clock_t clk = clock();
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
9848 KB |
Output is correct |
| 2 |
Correct |
20 ms |
9848 KB |
Output is correct |
| 3 |
Correct |
25 ms |
9976 KB |
Output is correct |
| 4 |
Correct |
617 ms |
17776 KB |
Output is correct |
| 5 |
Correct |
1620 ms |
28012 KB |
Output is correct |
| 6 |
Runtime error |
2204 ms |
33792 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 7 |
Correct |
1083 ms |
23240 KB |
Output is correct |
| 8 |
Correct |
858 ms |
24440 KB |
Output is correct |
| 9 |
Correct |
1269 ms |
22688 KB |
Output is correct |
| 10 |
Correct |
2820 ms |
31484 KB |
Output is correct |
