Submission #210117

#TimeUsernameProblemLanguageResultExecution timeMemory
210117ZwariowanyMarcinRelativnost (COCI15_relativnost)C++14
0 / 140
3490 ms23896 KiB
#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) { a %= MOD; b %= MOD; pos += pod; dp[pos][0] = b; dp[pos][1] = a; x[pos] = (a + b) % MOD; for (pos /= 2; pos; pos /= 2) merge(pos); } 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 (stderr)

relativnost.cpp: In function 'int main()':
relativnost.cpp:51: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:54: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:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &q);
  ~~~~~~^~~~~~~~~~
relativnost.cpp:59: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 timeMemoryGrader output
Fetching results...