Submission #1193507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193507		InvMOD	Relativnost (COCI15_relativnost)	C++17	0 / 140	138 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[N << 2][C];

void add(int& x, int y){
    x += y;
    if(x >= MOD) x -= MOD;
}

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

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

void build(int id, int l, int r){
    if(l == r){
        st[id][0] = b[l] % MOD;
        st[id][1] = 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[id][0] = b[x] % MOD;
        st[id][1] = 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[1][c] << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 140