// 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);
rep(i,n)
{
scanf("%d",&a[i]);
}
rep(i,n)
{
scanf("%d",&b[i]);
}
node(0,n-1,1).build();
scanf("%d",&q);
while(q--)
{
int p;
scanf("%d",&p);p--;
scanf("%d%d",&a[p],&b[p]);
node(0,n-1,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);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 |
10 ms |
504 KB |
Output is correct |
| 2 |
Correct |
19 ms |
504 KB |
Output is correct |
| 3 |
Correct |
37 ms |
504 KB |
Output is correct |
| 4 |
Correct |
608 ms |
11896 KB |
Output is correct |
| 5 |
Correct |
2120 ms |
23200 KB |
Output is correct |
| 6 |
Correct |
3154 ms |
23128 KB |
Output is correct |
| 7 |
Correct |
1367 ms |
12204 KB |
Output is correct |
| 8 |
Correct |
714 ms |
22776 KB |
Output is correct |
| 9 |
Correct |
1316 ms |
23020 KB |
Output is correct |
| 10 |
Execution timed out |
4090 ms |
23080 KB |
Time limit exceeded |
