oj.uz

Submission #1094401

# Submission time Handle Problem Language Result Execution time Memory
1094401 2024-09-29T14:54:08 Z VMaksimoski008 Relativnost (COCI15_relativnost) C++17
42 / 140
 4000 ms 23124 KB 
#include <bits/stdc++.h>
using namespace std;

const int mod = 10007;
const int maxn = 1e5 + 5;

int tree[4*maxn][21], n, m;

void update(int u, int tl, int tr, int p, int a, int b) {
    if(tl == tr) {
        tree[u][1] = a;
        tree[u][0] = b;
    } else {
        int tm = (tl + tr) / 2;
        if(p <= tm) update(2*u, tl, tm, p, a, b);
        else update(2*u+1, tm+1, tr, p, a, b);
        for(int i=0; i<=m; i++) tree[u][i] = 0;
        for(int i=0; i<=m; i++)
            for(int j=0; j<=m; j++) tree[u][min(i+j, m)] = (tree[u][min(i+j, m)] + tree[2*u][i] * tree[2*u+1][j] % mod) % mod;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);
    
    cin >> n >> m;
    vector<int> A(n+1), B(n+1);
    for(int i=1; i<=n; i++) cin >> A[i];
    for(int i=1; i<=n; i++) cin >> B[i];
    for(int i=1; i<=n; i++) update(1, 1, n, i, A[i], B[i]);

    int q; cin >> q;
    int p, na, nb;
    while(q--) {
        cin >> p >> na >> nb;
        update(1, 1, n, p, na, nb);
        cout << tree[1][m] << '\n';
    }

    return 0;
}

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 600 KB Output is correct
2 Correct 15 ms 592 KB Output is correct
3 Correct 33 ms 604 KB Output is correct
4 Incorrect 567 ms 11992 KB Output isn't correct
5 Incorrect 2406 ms 22864 KB Output isn't correct
6 Execution timed out 4019 ms 22864 KB Time limit exceeded
7 Incorrect 1527 ms 11860 KB Output isn't correct
8 Incorrect 883 ms 23124 KB Output isn't correct
9 Incorrect 1215 ms 22868 KB Output isn't correct
10 Execution timed out 4070 ms 22692 KB Time limit exceeded