oj.uz

Submission #306218

# Submission time Handle Problem Language Result Execution time Memory
306218 2020-09-24T22:19:24 Z fishy15 Relativnost (COCI15_relativnost) C++14
0 / 140
 2883 ms 38136 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;
int a[MAXN];
int b[MAXN];

struct node {
    int 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] += 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++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    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
0 / 140.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 33280 KB Memory limit exceeded
2 Runtime error 32 ms 33280 KB Memory limit exceeded
3 Runtime error 42 ms 33280 KB Memory limit exceeded
4 Runtime error 392 ms 36880 KB Memory limit exceeded
5 Runtime error 1208 ms 38136 KB Memory limit exceeded
6 Runtime error 1847 ms 37732 KB Memory limit exceeded
7 Runtime error 834 ms 36876 KB Memory limit exceeded
8 Runtime error 435 ms 37240 KB Memory limit exceeded
9 Runtime error 800 ms 38136 KB Memory limit exceeded
10 Runtime error 2883 ms 38016 KB Memory limit exceeded