Submission #1193514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193514		InvMOD	Relativnost (COCI15_relativnost)	C++17	140 / 140	3595 ms	7196 KiB

relativnost

#include<bits/stdc++.h>

using namespace std;

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

int16_t c, a[N], b[N], st[C][N << 2];

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

    for(int16_t i = 0; i <= c; i++){
        for(int16_t j = 0; j <= c; j++){
            if(i + j <= c){
                st[i + j][id] = (st[i + j][id] + (1ll * st[i][id << 1] * st[j][id << 1|1])) % MOD;
            }
            else{
                st[c][id] = (st[c][id] + (1ll * st[i][id << 1] * st[j][id << 1|1])) % MOD;
            }
        }
    }
}

inline void update(int id, int l, int r, int x){
    if(l == r){
        st[0][id] = b[x];
        st[1][id] = a[x];
    }
    else{
        int m = l+r>>1;
        if(x <= m)
            update(id << 1, l, m, 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);

    int n,q; cin >> n >> c;
    for(int i = 1; i <= n; i++){
        int x; cin >> x;
        a[i] = x % MOD;
    }

    for(int i = 1; i <= n; i++){
        int x; cin >> x;
        b[i] = x % MOD;
    }

    for(int i = 1; i <= n; i++){
        update(1, 1, n, i);
    }

    cin >> q;
    while(q--){
        int p,x,y; cin >> p >> x >> y;

        a[p] = x % MOD;
        b[p] = y % MOD;

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

• Subtask 1: 140 / 140