Submission #1193509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193509		InvMOD	Relativnost (COCI15_relativnost)	C++17	0 / 140	172 ms	131072 KiB

relativnost

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 1, C = 21, MOD = 10007;

int n, q, c, a[N], b[N], st[C][N << 2];

void merge_st(int id){
    for(int i = 0; i <= c; i++) st[i][id] = 0;

    for(int i = 0; i <= c; i++){
        for(int j = 0; j <= c; j++){
            st[min(i + j, c)][id] = (st[min(i + j, c)][id] + st[i][id << 1] * st[j][id << 1|1]) % MOD;
        }
    }
}

void build(int id, int l, int r){
    if(l == r){
        st[0][id] = b[l] % MOD;
        st[1][id] = a[l] % MOD;
    }
    else{
        int m = l+r>>1;
        build(id << 1, l, m);
        build(id << 1|1, m+1, r);
        merge_st(id);
    }
}

void update(int id, int l, int r, int x){
    if(l == r){
        st[0][id] = b[x] % MOD;
        st[1][id] = a[x] % MOD;
    }
    else{
        int m = l+r>>1;
        if(x <= m)
            update(id << 1, l, r, x);
        else update(id << 1|1, m+1, r, x);
        merge_st(id);
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.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];

    build(1, 1, n);

    cin >> q;
    while(q--){
        int p; cin >> p >> a[p] >> b[p];

        update(1, 1, n, p);
        cout << st[c][1] << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 140