oj.uz

Submission #306219

# Submission time Handle Problem Language Result Execution time Memory
306219 2020-09-24T22:27:34 Z fishy15 Relativnost (COCI15_relativnost) C++14
140 / 140
 2793 ms 17784 KB 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>

#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 10007

#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f

// change if necessary
#define MAXN 100001

using namespace std;

int n, c, q;
short a[MAXN];
short b[MAXN];

struct node {
    short nums[21];
    node() { memset(nums, 0, sizeof nums); nums[0] = 1; }
    node(int a, int b) {
        memset(nums, 0, sizeof nums);
        nums[0] = b % MOD;
        nums[1] = a % MOD;
    }
    node operator*(const node &b) {
        node ans;
        ans.nums[0] = 0;
        for (int i = 0; i <= c; i++) {
            for (int j = 0; j <= c; j++) {
                int p = min(i + j, c);
                ans.nums[p] += (int) nums[i] * b.nums[j] % MOD;
                if (ans.nums[p] >= MOD) ans.nums[p] -= MOD;
            }
        }
        return ans;
    }
};

node st[4 * MAXN];

void build(int v, int l, int r) {
    if (l == r) {
        st[v] = node(a[l], b[r]);
    } else {
        int m = (l + r) / 2;
        build(2 * v, l, m);
        build(2 * v + 1, m + 1, r);
        st[v] = st[2 * v] * st[2 * v + 1];
    }
}

void upd(int v, int l, int r, int x, int a, int b) {
    if (l == r) {
        st[v] = node(a, b);
        ::a[x] = a;
        ::b[x] = b;
    } else {
        int m = (l + r) / 2;
        if (x <= m) {
            upd(2 * v, l, m, x, a, b);
        } else {
            upd(2 * v + 1, m + 1, r, x, a, b);
        }
        st[v] = st[2 * v] * st[2 * v + 1];
    }
}

node qry(int v, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        return st[v];
    } else if (r < x || l > y) {
        return node();
    } else {
        int m = (l + r) / 2;
        return qry(2 * v, l, m, x, y) * qry(2 * v + 1, m + 1, r, x, y);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

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

    build(1, 0, n - 1);

    cin >> q;
    while (q--) {
        int p, a, b; cin >> p >> a >> b;
        p--;
        upd(1, 0, n - 1, p, a, b);
        cout << qry(1, 0, n - 1, 0, n - 1).nums[c] << '\n';
    }

    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16768 KB Output is correct
2 Correct 20 ms 16768 KB Output is correct
3 Correct 33 ms 16768 KB Output is correct
4 Correct 372 ms 17272 KB Output is correct
5 Correct 1199 ms 17616 KB Output is correct
6 Correct 1750 ms 17616 KB Output is correct
7 Correct 782 ms 17272 KB Output is correct
8 Correct 415 ms 17272 KB Output is correct
9 Correct 755 ms 17784 KB Output is correct
10 Correct 2793 ms 17784 KB Output is correct