제출 #1125044

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

relativnost

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

const int mod = 1e4 + 7;

ll tree[200005][21];
int n, c, q, p, x, y;

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;
    }
}

int main() {
    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]);

    cin >> q;
    while(q--) {
        cin >> p >> x >> y;
        update(p-1, x, y);
        cout << tree[1][c] << '\n';
    }
}

• Subtask 1: 140 / 140