oj.uz

답안 #1016038

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1016038 2024-07-07T10:09:48 Z May27_th Relativnost (COCI15_relativnost) C++17
28 / 140
 3202 ms 27028 KB 
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define i128 __int128
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
const int MOD = 10007;
int C;
struct Tree {
  int N; 
  vector<vector<int16_t>> st;
  Tree (int _N) : N(_N), st(_N * 4 + 10) {
    for (int i = 1; i <= 4 * N + 8; i ++) {
      st[i].resize(C + 2, 0);
    }
  }
  void update(int id, int l, int r, int p, pair<int16_t, int16_t> x) {
    if (p < l || p > r) return;
    if (l == r) {
      st[id][0] = x.second;
      st[id][1] = x.first;
      return;
    }
    int mid = (l + r)/2;
    update(id * 2, l, mid, p, x);
    update(id * 2 + 1, mid + 1, r, p, x);

    for (int i = 0; i <= C; i ++) st[id][i] = 0;
    for (int i = 0; i <= C; i ++) {
      for (int j = 0; j <= C; j ++) {
        int p = min(i + j, C);
        st[id][p] += (st[id * 2][i] * st[id * 2 + 1][j]) % MOD;
        if (st[id][p] > MOD) st[id][p] -= MOD;
      }
    }
  }
};
void Solve(void) {
  int N; cin >> N >> C;
  vector<pair<int, int>> p(N);
  for (int i = 0; i < N; i ++) cin >> p[i].first;
  for (int i = 0; i < N; i ++) cin >> p[i].second;  
  Tree T(N);
  for (int i = 0; i < N; i ++) {
    p[i].first %= MOD;
    p[i].second %= MOD;
    T.update(1, 1, N, i + 1, p[i]);
  }
  // cout << T.st[1].f[C] << "\n";
  int Q; cin >> Q; while (Q --) {
    int p, A, B; cin >> p >> A >> B;
    A %= MOD; B %= MOD;
    T.update(1, 1, N, p, mp(A, B));
    cout << T.st[1][C] << "\n";
  }
}
signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(10);
  int Tests = 1; // cin >> Tests;
  while (Tests --) {
    Solve();
  }
}

Subtask #1
28.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 604 KB Output is correct
2 Correct 11 ms 604 KB Output is correct
3 Incorrect 22 ms 712 KB Output isn't correct
4 Incorrect 401 ms 12604 KB Output isn't correct
5 Incorrect 1552 ms 25452 KB Output isn't correct
6 Incorrect 2556 ms 27028 KB Output isn't correct
7 Incorrect 948 ms 19000 KB Output isn't correct
8 Incorrect 590 ms 21240 KB Output isn't correct
9 Incorrect 790 ms 17568 KB Output isn't correct
10 Incorrect 3202 ms 25480 KB Output isn't correct