#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;
void enter()
{
cin >> n >> c;
for(int i = 1 ; i <= n ; ++i)cin >> a[i];
for(int i = 1 ; i <= n ; ++i)cin >> b[i];
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],(ll)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 , int p){
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 , p);
else update(x * 2 + 1 , mid + 1 , r , p);
Merge(s[x], s[x * 2],s[x * 2 + 1]);
}
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);
// cout << s[1].dp[0] << endl;
int res = 1;
for(int i = 1 ; i <= n ; ++i)res = (ll)res * (a[i] + b[i]) % mod;
while(q--){
int p;cin >> p;
res = (ll)res * Pow(a[p] + b[p],mod-2) % mod;
cin >> a[p] >> b[p];
res = (ll)res * (a[p] + b[p]) % mod;
update(1,1,n,p);
int tmpres = res;
for(int j = 0 ; j < c ; ++j){
tmpres -= s[1].dp[j];
// cout << 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:58:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
relativnost.cpp: In function 'void update(int, int, int, int)':
relativnost.cpp:70:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
relativnost.cpp: In function 'int main()':
relativnost.cpp:81: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:81: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 |
31744 KB |
Output is correct |
| 2 |
Correct |
33 ms |
31716 KB |
Output is correct |
| 3 |
Correct |
36 ms |
31616 KB |
Output is correct |
| 4 |
Correct |
241 ms |
32504 KB |
Output is correct |
| 5 |
Runtime error |
705 ms |
32888 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 6 |
Runtime error |
1056 ms |
32808 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 7 |
Correct |
452 ms |
32544 KB |
Output is correct |
| 8 |
Correct |
272 ms |
32608 KB |
Output is correct |
| 9 |
Runtime error |
450 ms |
32776 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 10 |
Correct |
1220 ms |
32748 KB |
Output is correct |
