// 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 = 1e9+7;
const int N = 1e5+7;
const int C = 27;
int n,c,q;
int a[N],b[N],st[N*4][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;
}
}
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> c;
repA(i,1,n)
{
cin >> a[i] >> b[i];
node(1,n,1).update(i);
}
cin >> q;
while(q--)
{
int p;
cin >> p;
cin >> a[p] >> b[p];
node(1,n,1).update(p);
cout << st[1][c] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
632 KB |
Output isn't correct |
| 2 |
Incorrect |
26 ms |
632 KB |
Output isn't correct |
| 3 |
Incorrect |
52 ms |
576 KB |
Output isn't correct |
| 4 |
Incorrect |
945 ms |
18092 KB |
Output isn't correct |
| 5 |
Runtime error |
3921 ms |
33368 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 6 |
Execution timed out |
4034 ms |
30896 KB |
Time limit exceeded |
| 7 |
Incorrect |
2472 ms |
18348 KB |
Output isn't correct |
| 8 |
Incorrect |
1488 ms |
32572 KB |
Output isn't correct |
| 9 |
Runtime error |
2116 ms |
33616 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 10 |
Execution timed out |
4006 ms |
30440 KB |
Time limit exceeded |
