oj.uz

Submission #1016007

# Submission time Handle Problem Language Result Execution time Memory
1016007 2024-07-07T09:38:59 Z May27_th Relativnost (COCI15_relativnost) C++17
56 / 140
 4000 ms 65536 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 {
  struct Data {
    vector<i64> f;
    Data () {
      f.resize(C + 2, 0);
    }
  };
  int N; 
  vector<Data> st;
  Tree (int _N) : N(_N), st(_N * 4 + 4) {}
  Data combine(Data L, Data R) {
    Data res;
    for (int i = 0; i <= C; i ++) {
      for (int j = 0; j <= C; j ++) {
        i64 &add = res.f[min(i + j, C)];
        add = (add + L.f[i] * R.f[j] % MOD) % MOD;
        // cout << i << " " << j << " " << res.f[min(i + j, C)] << " " << L.f[i] << " " << R.f[j] << "\n";
      }
    }
    return res;
  };
  void update(int id, int l, int r, int p, pair<int, int> x) {
    if (p < l || p > r) return;
    if (l == r) {
      st[id].f[0] = x.second;
      st[id].f[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);
    st[id] = combine(st[id * 2], st[id * 2 + 1]);
  }
};
void Solve(void) {
  int N; cin >> N >> C;
  vector<int> a(N + 2), b(N + 2);
  for (int i = 1; i <= N; i ++) cin >> a[i];
  for (int i = 1; i <= N; i ++) cin >> b[i];
  
  Tree T(N);
  for (int i = 1; i <= N; i ++) {
    T.update(1, 1, N, i, mp(a[i], b[i]));
  }
  // cout << T.st[1].f[C] << "\n";
  int Q; cin >> Q; while (Q --) {
    int p, A, B; cin >> p >> A >> B;
    T.update(1, 1, N, p, mp(A, B));
    cout << T.st[1].f[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
56.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 860 KB Output is correct
2 Correct 16 ms 896 KB Output is correct
3 Correct 32 ms 856 KB Output is correct
4 Correct 628 ms 25168 KB Output is correct
5 Runtime error 2226 ms 56148 KB Memory limit exceeded
6 Runtime error 45 ms 65536 KB Execution killed with signal 9
7 Runtime error 1439 ms 41552 KB Memory limit exceeded
8 Runtime error 946 ms 46828 KB Memory limit exceeded
9 Runtime error 1221 ms 39960 KB Memory limit exceeded
10 Execution timed out 4059 ms 64048 KB Time limit exceeded