oj.uz

답안 #251660

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251660 2020-07-22T06:41:11 Z VEGAnn Relativnost (COCI15_relativnost) C++14
42 / 140
 2767 ms 26436 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100100;
const int C = 22;
const int md = 10007;
int n, c, a[N], b[N], st[4 * N][C];

int mult(int x, int y) { return (x * y) % md; }

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

void clear(int v){
    for (int i = 0; i <= c; i++)
        st[v][i] = 0;
}

void combine(int v, int l, int r){
    clear(v);

    for (int i = 0; i <= c; i++)
    for (int j = 0; j <= c; j++)
        SUM(st[v][min(i + j, c)], mult(st[l][i], st[r][j]));
}

void build(int v, int l, int r){
    if (l == r){
        clear(v);
        st[v][0] = b[l];
        st[v][1] = a[l];
        return;
    }

    int md = (l + r) >> 1;

    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    combine(v, v + v, v + v + 1);
}

void update(int v, int l, int r, int ps){
    if (l == r){
        clear(v);
        st[v][0] = b[l];
        st[v][1] = a[l];
        return;
    }

    int md = (l + r) >> 1;

    if (ps <= md)
        update(v + v, l, md, ps);
    else update(v + v + 1, md + 1, r, ps);

    combine(v, v + v, v + v + 1);
}

int main() {
#ifdef _LOCAL
    freopen("in.txt","r",stdin); // freopen("output.txt","w",stdout);
#else
//    freopen("mining.in","r",stdin); freopen("mining.out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
#endif

    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);

    int qq; cin >> qq;

    for (; qq; qq--){
        int ps, an, bn; cin >> ps >> an >> bn;

        a[ps] = an;
        b[ps] = bn;

        update(1, 1, n, ps);

        cout << st[1][c] << '\n';
    }

    return 0;
}

Subtask #1
42.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 12 ms 512 KB Output is correct
3 Correct 20 ms 384 KB Output is correct
4 Incorrect 355 ms 13948 KB Output isn't correct
5 Incorrect 1198 ms 25976 KB Output isn't correct
6 Incorrect 1747 ms 25928 KB Output isn't correct
7 Incorrect 762 ms 13968 KB Output isn't correct
8 Incorrect 406 ms 25360 KB Output isn't correct
9 Incorrect 774 ms 26372 KB Output isn't correct
10 Incorrect 2767 ms 26436 KB Output isn't correct