제출 #1125042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125042		VMaksimoski008	Relativnost (COCI15_relativnost)	C++17	42 / 140	3127 ms	16456 KiB

relativnost

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mod = 1e4 + 7;

int tree[200005][21], n, c;

void update(int p, int a, int b) {
    p += n;
    tree[p][0] = b;
    tree[p][1] = a;

    for(; p>1; p>>=1) {
        for(int i=0; i<=c; i++) tree[p>>1][i] = 0;
        for(int i=0; i<=c; i++) 
            for(int j=0; j<=c; j++)
                tree[p>>1][min(c,i+j)] = (tree[p>>1][min(c,i+j)] + tree[p][i] * tree[p^1][j]) % mod;
    }
}

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

    cin >> n >> c;
    vector<int> a(n), b(n);
    for(int &x : a) cin >> x;
    for(int &x : b) cin >> x;
    for(int i=0; i<n; i++) update(i, a[i], b[i]);

    int q; cin >> q;
    while(q--) {
        int p, a, b; cin >> p >> a >> b;
        update(p-1, a, b);
        cout << tree[1][c] << '\n';
    }
    
    return 0;
}

• Subtask 1: 42 / 140