#include<bits/stdc++.h>
using namespace std;
#define taskname "TEST"
#define pb push_back
typedef long double ld;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 1e4 + 7;
int n , c , a[maxn] , b[maxn];
int res = 0;
int q , p;
void enter()
{
cin >> n >> c;
for(int i = 1 ; i <= n ; ++i){
cin >> a[i];
a[i] %= mod;
}
for(int i = 1 ; i <= n ; ++i){
cin >> b[i];
b[i] %= mod;
}
cin >> q;
}
int Pow(int a , int b){
if(b == 0)return 1;
int r = Pow(a , b / 2);
if(b & 1)return (ll)r * r % mod * a % mod;
return (ll)r * r % mod;
}
void add(int & x , int y){
x += y;
if(x < 0)x += mod;
if(x >= mod)x -= mod;
}
struct node{
int dp[20];
node(){fill_n(dp,20,0);};
}s[maxn * 4];
//20 * maxn * 4 = 8e6
void Merge(node & res , const node & x , const node & other) {
fill_n(res.dp,20,0);
for(int i = 0 ; i < c ; ++i){
for(int j = 0 ; j < c - i ; ++j){
add(res.dp[i + j],x.dp[i] * other.dp[j] % mod);
}
}
}
void build(int x , int l , int r){
if(l == r){
s[x].dp[0] = b[l];
s[x].dp[1] = a[l];
return;
}
int mid = l + r >> 1;
build(x * 2 , l , mid);
build(x * 2 + 1 , mid + 1 , r);
Merge(s[x], s[x * 2],s[x * 2 + 1]);
}
void update(int x , int l , int r){
if(l == r){
s[x].dp[0] = b[l];
s[x].dp[1] = a[l];
return;
}
int mid = l + r >> 1;
if(mid >= p)update(x * 2 , l , mid);
else update(x * 2 + 1 , mid + 1 , r);
Merge(s[x], s[x * 2],s[x * 2 + 1]);
}
int inv[mod];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".INP","r"))
freopen(taskname".INP", "r",stdin) ,
freopen(taskname".OUT", "w",stdout);
enter();
build(1,1,n);
int res = 1;
for(int i = 1 ; i < mod ; ++i)inv[i] = Pow(i,mod-2);
for(int i = 1 ; i <= n ; ++i)res = (ll)res * (a[i] + b[i]) % mod;
while(q--){
cin >> p;
res = res * inv[(a[p] + b[p]) % mod] % mod;
cin >> a[p] >> b[p];
a[p] %= mod;b[p] %= mod;
res = res * (a[p] + b[p]) % mod;
update(1,1,n);
int tmpres = res;
for(int j = 0 ; j < c ; ++j){
tmpres -= s[1].dp[j];
if(tmpres < 0)tmpres += mod;
}
cout << tmpres << '\n';
}
}
Compilation message
relativnost.cpp: In function 'void build(int, int, int)':
relativnost.cpp:64:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
relativnost.cpp: In function 'void update(int, int, int)':
relativnost.cpp:76:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
relativnost.cpp: In function 'int main()':
relativnost.cpp:88:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".INP", "r",stdin) ,
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
freopen(taskname".OUT", "w",stdout);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
relativnost.cpp:88:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
36 ms |
31864 KB |
Output is correct |
| 2 |
Correct |
39 ms |
31736 KB |
Output is correct |
| 3 |
Correct |
41 ms |
31736 KB |
Output is correct |
| 4 |
Correct |
236 ms |
32508 KB |
Output is correct |
| 5 |
Runtime error |
611 ms |
32888 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 6 |
Runtime error |
886 ms |
32888 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 7 |
Correct |
418 ms |
32512 KB |
Output is correct |
| 8 |
Correct |
305 ms |
32500 KB |
Output is correct |
| 9 |
Runtime error |
481 ms |
32888 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 10 |
Runtime error |
1396 ms |
32776 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
