#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define popb pop_back
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
const int mod = 1e4 + 7;
const int inf = 1e15;
int n, c;
int a[100001], b[100001];
int t[400001][21];
void merge(int v) {
for(int i = 0; i <= c; i++) t[v][i] = 0;
for(int i = 0; i <= c; i++) {
for(int j = 0; j <= c; j++) {
(t[v][min(c, i + j)] += t[2 * v][i] * t[2 * v + 1][j]) %= mod;
}
}
}
void build(int v, int tl, int tr) {
if(tl == tr) {
(t[v][1] = a[tl]) %= mod;
(t[v][0] = b[tl]) %= mod;
return;
}
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
merge(v);
}
void update(int v, int tl, int tr, int x) {
if(tl == tr) {
(t[v][1] = a[x]) %= mod;
(t[v][0] = b[x]) %= mod;
return;
}
int tm = (tl + tr) / 2;
if(x <= tm) {
update(2 * v, tl, tm, x);
} else update(2 * v + 1, tm + 1, tr, x);
merge(v);
}
void solve() {
cin >> n >> c;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
build(1, 1, n);
int q;
cin >> q;
while(q--) {
int p;
cin >> p >> a[p] >> b[p];
update(1, 1, n, p);
cout << t[1][c] << '\n';
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int t = 1;
//cin >> t;
while(t--) {
solve();
cout << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4700 KB |
Output isn't correct |
| 2 |
Incorrect |
9 ms |
2652 KB |
Output isn't correct |
| 3 |
Incorrect |
17 ms |
604 KB |
Output isn't correct |
| 4 |
Incorrect |
295 ms |
27796 KB |
Output isn't correct |
| 5 |
Runtime error |
985 ms |
50804 KB |
Memory limit exceeded |
| 6 |
Runtime error |
1549 ms |
50532 KB |
Memory limit exceeded |
| 7 |
Incorrect |
623 ms |
27772 KB |
Output isn't correct |
| 8 |
Runtime error |
351 ms |
50004 KB |
Memory limit exceeded |
| 9 |
Runtime error |
595 ms |
50772 KB |
Memory limit exceeded |
| 10 |
Runtime error |
2333 ms |
47444 KB |
Memory limit exceeded |
