#include <bits/stdc++.h>
#define LL long long
#define LD long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep2(i, j, n) for (LL i = j; i <= n; ++i)
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define boost cin.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(), x.end()
using namespace std;
const int MOD = 1e4 + 7;
const int pod = (1 << 17);
void add(int &a, int b) {
a += b;
if (a >= MOD) a -= MOD;
}
int n, c, a, b, f, q;
int dp[2 * pod][21];
int x[2 * pod];
void merge(int u) {
int p1 = 2 * u, p2 = 2 * u + 1;
x[u] = x[p1] * x[p2] % MOD;
rep(i, 0, c - 1) dp[u][i] = 0;
rep(i, 0, c - 1)
rep(j, 0, c - 1 - i)
add(dp[u][i + j], dp[p1][i] * dp[p2][j] % MOD);
}
void upd(int pos, int a, int b) {
pos += pod;
dp[pos][0] = b;
dp[pos][1] = a;
x[pos] = (a + b) % MOD;
pos /= 2;
while (pos) {
merge(pos);
pos /= 2;
}
}
int main() {
scanf ("%d%d", &n, &c);
rep(i, 0, pod - 1) upd(i, 0, 1);
rep(i, 1, n) {
scanf ("%d%d", &a, &b);
upd(i, a, b);
}
scanf ("%d", &q);
while (q--) {
scanf ("%d%d%d", &f, &a, &b);
upd(f, a, b);
int sum = 0;
rep(i, 0, c - 1) add(sum, dp[1][i]);
printf ("%d\n", (x[1] - sum + MOD) % MOD);
}
return 0;
}
Compilation message
relativnost.cpp: In function 'int main()':
relativnost.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &n, &c);
~~~~~~^~~~~~~~~~~~~~~~
relativnost.cpp:56:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &a, &b);
~~~~~~^~~~~~~~~~~~~~~~
relativnost.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &q);
~~~~~~^~~~~~~~~~
relativnost.cpp:61:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d%d", &f, &a, &b);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
363 ms |
23088 KB |
Output isn't correct |
| 2 |
Incorrect |
487 ms |
22904 KB |
Output isn't correct |
| 3 |
Incorrect |
1393 ms |
22904 KB |
Output isn't correct |
| 4 |
Incorrect |
527 ms |
25976 KB |
Output isn't correct |
| 5 |
Incorrect |
1558 ms |
27140 KB |
Output isn't correct |
| 6 |
Incorrect |
2789 ms |
26616 KB |
Output isn't correct |
| 7 |
Incorrect |
1190 ms |
25976 KB |
Output isn't correct |
| 8 |
Incorrect |
677 ms |
26348 KB |
Output isn't correct |
| 9 |
Incorrect |
964 ms |
27388 KB |
Output isn't correct |
| 10 |
Incorrect |
3642 ms |
27000 KB |
Output isn't correct |
