#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long int lld;
#define MOD 10007
int n,c;
int Segtree[400000][30];
int A[100000];
int B[100000];
void build(int a, int b, int node){
if(a==b){
for(int i=0;i<=c;i++){
Segtree[node][i]=0;
}
Segtree[node][0]=B[a];
Segtree[node][1]=A[a];
return;
}
int mid=(a+b)/2;
build(a,mid,2*node);
build(mid+1,b,2*node+1);
for(int i=0;i<=c;i++){
Segtree[node][i]=0;
}
for(int i=0;i<=c;i++){
for(int j=0;j<=c;j++){
Segtree[node][min(i+j,c)]+=Segtree[2*node][i]*Segtree[2*node+1][j];
Segtree[node][min(i+j,c)]%=MOD;
}
}
}
void update(int a,int b, int node, int x){
//cout<<a<<" "<<b<<endl;
if(x<a || b<x)return;
if(a==b){
for(int i=0;i<=c;i++){
Segtree[node][i]=0;
}
Segtree[node][0]=B[a];
Segtree[node][1]=A[a];
return;
}
int mid=(a+b)/2;
update(a,mid,2*node,x);
update(mid+1,b,2*node+1,x);
for(int i=0;i<=c;i++){
Segtree[node][i]=0;
}
for(int i=0;i<=c;i++){
for(int j=0;j<=c;j++){
Segtree[node][min(i+j,c)]+=Segtree[2*node][i]*Segtree[2*node+1][j];
Segtree[node][min(i+j,c)]%=MOD;
}
}
}
int main(){
cin>>n>>c;
for(int i=0;i<n;i++)cin>>A[i];
for(int i=0;i<n;i++)cin>>B[i];
build(0,n-1,1);
int q;
cin>>q;
while(q--){
int x;
cin>>x;
x--;
lld y,z;
cin>>y>>z;
A[x]=y;
B[x]=z;
update(0,n-1,1,x);
cout<<Segtree[1][c]<<endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
632 KB |
Output is correct |
| 2 |
Correct |
18 ms |
764 KB |
Output is correct |
| 3 |
Correct |
30 ms |
764 KB |
Output is correct |
| 4 |
Incorrect |
673 ms |
18224 KB |
Output isn't correct |
| 5 |
Runtime error |
1756 ms |
33792 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 6 |
Runtime error |
2497 ms |
33792 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 7 |
Runtime error |
1187 ms |
33792 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 8 |
Runtime error |
755 ms |
33792 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 9 |
Runtime error |
1251 ms |
33792 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 10 |
Runtime error |
3903 ms |
33792 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
