Submission #98655

#	Time	Username	Problem	Language	Result	Execution time	Memory
98655		minhtung0404	Relativnost (COCI15_relativnost)	C++17	140 / 140	3427 ms	23180 KiB

relativnost

#include<bits/stdc++.h>
const int N = 1e5 + 5;
const int mod = 1e4 + 7;
using namespace std;

struct node{
    int ans[21];
} it[N << 2];
int n, c, q, sum, a[N], b[N];

void add(int& a, int b){
    a += b; a %= mod;
}

void Merge(node& ans, node& a, node& b){
    for (int i = 0; i <= c; i++) ans.ans[i] = 0;
    for (int i = 0; i <= c; i++) for (int j = 0; j <= c; j++) add(ans.ans[min(c, i+j)], a.ans[i] * b.ans[j]);
}

void init(int i, int l, int r){
    if (l == r){
        it[i].ans[0] = b[l];
        it[i].ans[1] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    init(i << 1, l, mid); init(i << 1 | 1, mid+1, r);
    Merge(it[i], it[i << 1], it[i << 1 | 1]);
}

void update(int i, int l, int r, int p, int a, int b){
    if (l > p || p > r) return;
    if (l == r){
        it[i].ans[0] = b;
        it[i].ans[1] = a;
        return;
    }
    int mid = (l + r) >> 1;
    update(i << 1, l, mid, p, a, b); update(i << 1 | 1, mid+1, r, p, a, b);
    Merge(it[i], it[i << 1], it[i << 1 | 1]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> c;
    for (int i = 1; i <= n; i++) cin >> a[i], a[i] %= mod;
    for (int i = 1; i <= n; i++) cin >> b[i], b[i] %= mod;
    init(1, 1, n);
    cin >> q;
    while (q--){
        int p, a1, b1;
        cin >> p >> a1 >> b1;
        update(1, 1, n, p, a1 % mod, b1 % mod);
        cout << it[1].ans[c] << "\n";
    }
}

• Subtask 1: 140 / 140