oj.uz

답안 #697278

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697278 2023-02-09T05:11:09 Z kusssso Relativnost (COCI15_relativnost) C++17
0 / 140
 960 ms 65536 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
const int N = 1e5 + 5;
const int mod = 10007;
int n, c;
int q;
int a[N];
int b[N];
struct Node {
      ll tot;
      vi dp;
}
st[4 * N];

void update (int p, ll va, ll vb, int x = 1, int L = 1, int R = n) {
      if (L > p || R < p) return;
      if (L == R && R == p) {
            st[x].tot = (va + vb) % mod;
            st[x].dp[0] = vb;
            st[x].dp[1] = va;
            return;
      }
      int mid = (L + R) / 2;
      update(p, va, vb, x * 2, L, mid);
      update(p, va, vb, x * 2 + 1, mid + 1, R);
      st[x].tot = st[x * 2].tot * st[x * 2 + 1].tot % mod;
      for (int k = 0; k < c; k++) {
            st[x].dp[k] = 0;
            for (int i = 0; i <= k; i++) {
                  st[x].dp[k] = (st[x].dp[k] + st[x * 2].dp[i] * st[x * 2 + 1].dp[k - i] % mod) % mod;
            }
      }
}

signed main() {
      ios_base::sync_with_stdio(0);
      cin.tie(0);
      cin >> n >> c;
      for (int i = 1; i <= n; i++) cin >> a[i];
      for (int i = 1; i <= n; i++) cin >> b[i];
      for (int i = 0; i < 4 * N; i++) st[i].dp.resize(c, 0);
      for (int i = 1; i <= n; i++) update(i, a[i], b[i]);
      cin >> q;
      while (q--) {
            int i, na, nb;
            cin >> i >> na >> nb;
            a[i] = na;
            b[i] = nb;
            update(i, na, nb);
            ll total = st[1].tot;
            ll bad = 0;
            // cout << '#' << st[1].dp[0] << '\n';
            for (int k = 0; k < c; k++) bad = (bad + st[1].dp[k]) % mod;
            cout << (total + mod - bad) % mod << '\n';
      }
      return 0;
}

Subtask #1
0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 36 ms 44108 KB Memory limit exceeded
2 Runtime error 41 ms 50348 KB Memory limit exceeded
3 Runtime error 40 ms 65536 KB Execution killed with signal 9
4 Runtime error 272 ms 41188 KB Memory limit exceeded
5 Runtime error 960 ms 61428 KB Memory limit exceeded
6 Runtime error 55 ms 65536 KB Execution killed with signal 9
7 Runtime error 615 ms 60184 KB Memory limit exceeded
8 Runtime error 394 ms 48196 KB Memory limit exceeded
9 Runtime error 563 ms 48988 KB Memory limit exceeded
10 Runtime error 52 ms 65536 KB Execution killed with signal 9