// Created by AboAbdoMC
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lll long long
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
const int OO = 1e4+7;
const int MOD = 1e4+7;
const int N = 1e5+7;
const int C = 21;
int n,c,q;
int a[N],b[N],st[N*3][C];
struct node {
int ll, rr, id;
node(int L, int R, int X) {
ll=L, rr=R, id=X;
}
node left()
{ return node(ll, (ll+rr)/2, id*2); }
node right()
{ return node((ll+rr)/2+1, rr, id*2+1); }
void update(int pos){ // don't need to call lazy_update() at the beginning
repA(i,0,c) st[id][i] = 0;
if (ll == rr)
{
st[id][0] = b[pos]%MOD;
st[id][1] = a[pos]%MOD;
return;
}
if (pos <= (ll+rr)/2) left().update(pos); // easier to read
else right().update(pos);
repA(i,0,c)
{
repA(j,0,c)
{
int k = min(i+j,c);
st[id][k] += (st[right().id][i]*st[left().id][j])%MOD;
st[id][k] %= MOD;
}
}
}
void build()
{
if (ll == rr)
{
st[id][0] = b[ll]%MOD;
st[id][1] = a[ll]%MOD;
return;
}
left().build();
right().build();
repA(i,0,c)
{
repA(j,0,c)
{
int k = min(i+j,c);
st[id][k] += (st[right().id][i]*st[left().id][j])%MOD;
st[id][k] %= MOD;
}
}
}
};
int main()
{
scanf("%d%d",&n,&c);
repA(i,1,n)
{
scanf("%d",&a[i]);
}
repA(i,1,n)
{
scanf("%d",&b[i]);
}
node(1,n,1).build();
scanf("%d",&q);
while(q--)
{
int p;
scanf("%d",&p);
scanf("%d%d",&a[p],&b[p]);
node(1,n,1).update(p);
printf("%d\n",st[1][c]);
}
return 0;
}
Compilation message
relativnost.cpp: In function 'int main()':
relativnost.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&c);
~~~~~^~~~~~~~~~~~~~
relativnost.cpp:93:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
~~~~~^~~~~~~~~~~~
relativnost.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&b[i]);
~~~~~^~~~~~~~~~~~
relativnost.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
relativnost.cpp:108:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&p);
~~~~~^~~~~~~~~
relativnost.cpp:109:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a[p],&b[p]);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
504 KB |
Output is correct |
| 2 |
Correct |
23 ms |
504 KB |
Output is correct |
| 3 |
Correct |
38 ms |
508 KB |
Output is correct |
| 4 |
Correct |
617 ms |
12108 KB |
Output is correct |
| 5 |
Correct |
2098 ms |
23088 KB |
Output is correct |
| 6 |
Correct |
3173 ms |
24480 KB |
Output is correct |
| 7 |
Correct |
1369 ms |
12024 KB |
Output is correct |
| 8 |
Correct |
705 ms |
22900 KB |
Output is correct |
| 9 |
Correct |
1310 ms |
23088 KB |
Output is correct |
| 10 |
Execution timed out |
4026 ms |
24520 KB |
Time limit exceeded |
