oj.uz

Submission #93614

# Submission time Handle Problem Language Result Execution time Memory
93614 2019-01-10T11:03:08 Z dfistric Relativnost (COCI15_relativnost) C++14
0 / 140
 4000 ms 23584 KB 
#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) FOR(i, 0, n)
#define ll long long

using namespace std;

const int OFF = (1 << 17);
const int MOD = 10009;
int tour[2 * OFF][22];
int C;

int add(int a, int b) {
  return (a + b) % MOD;
}

int mul(int a, int b) {
  return (a * b) % MOD;
}

int pot(int v, int a) {
  int out = 1, p = v;
  while (a) {
    if (a & 1) out = mul(out, p);
    p = mul(p, p);
    a /= 2;
  }
  return out;
}

void update(int x, int a, int b) {
  x += OFF;
  tour[x][0] = b;
  tour[x][1] = a;
  x /= 2;

  while (x) {
    REP(i, C + 1) tour[x][i] = 0;
    REP(i, C + 1) {
      REP(j, C + 1) {
        tour[x][min(C, i + j)] = add(tour[x][min(C, i + j)], mul(tour[x * 2][i], tour[x * 2 + 1][j]));
      }
    }
    x /= 2;
  }

  return;
}

int main() {
  ios_base::sync_with_stdio(false);

  int n, a, b, x;
  cin >> n >> C;
  REP(i, 2 * OFF) tour[i][0] = 1;

  REP(i, n) {
    cin >> a >> b;
    update(i, a, b);
  }

  int q;
  cin >> q;
  REP(i, q) {
    cin >> x >> a >> b;
    update(x - 1, a, b);
    cout << tour[1][C] << "\n";
  }

  return 0;
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 22904 KB Output isn't correct
2 Incorrect 44 ms 22904 KB Output isn't correct
3 Incorrect 77 ms 23032 KB Output isn't correct
4 Incorrect 769 ms 23460 KB Output isn't correct
5 Incorrect 2768 ms 23452 KB Output isn't correct
6 Execution timed out 4083 ms 23424 KB Time limit exceeded
7 Incorrect 1815 ms 23284 KB Output isn't correct
8 Incorrect 1071 ms 23388 KB Output isn't correct
9 Incorrect 1547 ms 23584 KB Output isn't correct
10 Execution timed out 4017 ms 23280 KB Time limit exceeded