oj.uz

Submission #93630

# Submission time Handle Problem Language Result Execution time Memory
93630 2019-01-10T12:30:00 Z dfistric Relativnost (COCI15_relativnost) C++14
112 / 140
 4000 ms 9744 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 = 10007;
int tour[22][2 * OFF];
int A[OFF], B[OFF];
int C;

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

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

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

  while (x) {
    REP(i, C + 1) tour[i][x] = 0;

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

  return;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

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

  REP(i, n) cin >> A[i];
  REP(i, n) cin >> B[i];
  REP(i, n) update(i, A[i], B[i]);

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

  return 0;
}

Subtask #1
112.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1784 KB Output is correct
2 Correct 41 ms 1916 KB Output is correct
3 Correct 88 ms 2168 KB Output is correct
4 Correct 773 ms 4000 KB Output is correct
5 Correct 3590 ms 7704 KB Output is correct
6 Execution timed out 4043 ms 9744 KB Time limit exceeded
7 Correct 2301 ms 5972 KB Output is correct
8 Correct 1357 ms 5748 KB Output is correct
9 Correct 2013 ms 5744 KB Output is correct
10 Execution timed out 4061 ms 8648 KB Time limit exceeded