oj.uz

Submission #98655

# Submission time Handle Problem Language Result Execution time Memory
98655 2019-02-25T02:50:05 Z minhtung0404 Relativnost (COCI15_relativnost) C++17
140 / 140
 3427 ms 23180 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 512 KB Output is correct
2 Correct 15 ms 512 KB Output is correct
3 Correct 23 ms 512 KB Output is correct
4 Correct 458 ms 12000 KB Output is correct
5 Correct 1419 ms 23016 KB Output is correct
6 Correct 2182 ms 23180 KB Output is correct
7 Correct 922 ms 12116 KB Output is correct
8 Correct 528 ms 22808 KB Output is correct
9 Correct 897 ms 23076 KB Output is correct
10 Correct 3427 ms 22988 KB Output is correct