#include <cstdio>
#include <map>
#include <utility>
#include <cassert>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_LIM = lim,REPN = 1;REPN <= REPN_LIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("Line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ll = long long;
constexpr int maxn = 1e5 + 10,maxm = 20,mod = 1e4 + 7;
int qpow(int base,int b){
int res = 1;
while(b){
if(b & 1)res = res * base % mod;
base = base * base % mod;
b >>= 1;
}
return res;
}
int n,c,a[maxn],b[maxn];
namespace seg{
#define ls (x << 1)
#define rs (x << 1 | 1)
unsigned short val[maxn << 2][maxm];
void pushup(const int x){
rep(i,0,c - 1){
int s = 0;
rep(j,0,i)s += int(val[ls][j]) * val[rs][i - j];
val[x][i] = s % mod;
}
}
void build(const int l = 1,const int r = n,const int x = 1){
if(l == r){
let a = ::a[l],b = ::b[l];
val[x][0] = b % mod;
val[x][1] = a % mod;
return;
}
let mid = (l + r) >> 1;
build(l,mid,ls);
build(mid + 1,r,rs);
pushup(x);
}
void modify(const int p,const int a,const int b,const int l = 1,const int r = n,const int x = 1){
if(l == r){
val[x][0] = b % mod;
val[x][1] = a % mod;
return;
}
let mid = (l + r) >> 1;
if(p <= mid)modify(p,a,b,l,mid,ls);
else modify(p,a,b,mid + 1,r,rs);
pushup(x);
}
#undef ls
#undef rs
}
int ans = 1;
int main(){
// std::freopen("relativnost.in","r",stdin);
// std::freopen("relativnost.out","w",stdout);
std::scanf("%d %d",&n,&c);
rep(i,1,n)std::scanf("%d",a + i);
rep(i,1,n)std::scanf("%d",b + i);
rep(i,1,n)
a[i] %= mod,
b[i] %= mod,
ans = ans * ((a[i] + b[i]) % mod) % mod;
seg::build();
int q; std::scanf("%d",&q);
repn(q){
int p,x,y; std::scanf("%d %d %d",&p,&x,&y);
seg::modify(p,x,y);
ans = ans * qpow((a[p] + b[p]) % mod,mod - 2) % mod;
x %= mod,y %= mod;
ans = ans * ((x + y) % mod) % mod;
a[p] = x; b[p] = y;
int out = ans;
rep(i,0,c - 1)
out -= seg::val[1][i];
out %= mod;
out += mod;
out %= mod;
std::printf("%d\n",out);
}
std::fclose(stdin);
std::fclose(stdout);
return 0;
}
Compilation message
relativnost.cpp: In function 'int main()':
relativnost.cpp:64:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | std::scanf("%d %d",&n,&c);
| ~~~~~~~~~~^~~~~~~~~~~~~~~
relativnost.cpp:65:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | rep(i,1,n)std::scanf("%d",a + i);
| ~~~~~~~~~~^~~~~~~~~~~~
relativnost.cpp:66:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | rep(i,1,n)std::scanf("%d",b + i);
| ~~~~~~~~~~^~~~~~~~~~~~
relativnost.cpp:72:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | int q; std::scanf("%d",&q);
| ~~~~~~~~~~^~~~~~~~~
relativnost.cpp:74:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | int p,x,y; std::scanf("%d %d %d",&p,&x,&y);
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
| 2 |
Correct |
3 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
296 KB |
Output is correct |
| 4 |
Correct |
125 ms |
8312 KB |
Output is correct |
| 5 |
Correct |
217 ms |
13656 KB |
Output is correct |
| 6 |
Correct |
271 ms |
13712 KB |
Output is correct |
| 7 |
Correct |
176 ms |
8348 KB |
Output is correct |
| 8 |
Correct |
103 ms |
13312 KB |
Output is correct |
| 9 |
Correct |
164 ms |
13764 KB |
Output is correct |
| 10 |
Correct |
461 ms |
13600 KB |
Output is correct |
