oj.uz

Submission #648721

# Submission time Handle Problem Language Result Execution time Memory
648721 2022-10-07T19:26:17 Z Adominator Relativnost (COCI15_relativnost) C++17
140 / 140
 3451 ms 17044 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define ar array
#define vo vector
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()

#define rep(i, a, b) for(ll i=(a); i<(b); i++)
#define repd(i, a, b) for(ll i=(a); i>=(b); i--)

const int mxn=1e5+1, mod=1e4+7;
int n, c, q;
ar<int, 2> A[mxn];
int st[21][4*mxn];

void build(int v, int tl, int tr) {
    if(tl==tr) {
        st[0][v]=A[tl][1]%mod;
        st[1][v]=A[tl][0]%mod;
        return;
    }
    int tm=tl+(tr-tl)/2;
    build(v*2, tl, tm);
    build(v*2+1, tm+1, tr);
    rep(i, 0, c+1) {
        rep(j, 0, c+1) {
            st[min(ll(c), i+j)][v]+=st[i][v*2]*st[j][v*2+1]%mod;
            st[min(ll(c), i+j)][v]%=mod;
        }
    }
}

void upd(int v, int tl, int tr, int pos) {
    if(tl==tr) {
        st[0][v]=A[tl][1]%mod;
        st[1][v]=A[tl][0]%mod;
        return;
    }
    int tm=tl+(tr-tl)/2;
    if(pos<=tm)
        upd(v*2, tl, tm, pos);
    else
        upd(v*2+1, tm+1, tr, pos);

    rep(i, 0, c+1)
        st[i][v]=0;

    rep(i, 0, c+1) {
        rep(j, 0, c+1) {
            st[min(ll(c), i+j)][v]+=st[i][v*2]*st[j][v*2+1]%mod;
            st[min(ll(c), i+j)][v]%=mod;
        }
    }
}

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

    cin >> n >> c;

    rep(i, 0, n)
        cin >> A[i][0];

    rep(i, 0, n)
        cin >> A[i][1];

    build(1, 0, n-1);

    cin >> q;
    while(q--) {
        int p, a, b;
        cin >> p >> a >> b, --p;

        A[p]={a, b};
        upd(1, 0, n-1, p);

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

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 468 KB Output is correct
2 Correct 14 ms 596 KB Output is correct
3 Correct 25 ms 584 KB Output is correct
4 Correct 380 ms 6464 KB Output is correct
5 Correct 1379 ms 13488 KB Output is correct
6 Correct 2178 ms 15808 KB Output is correct
7 Correct 919 ms 7908 KB Output is correct
8 Correct 442 ms 10032 KB Output is correct
9 Correct 889 ms 11700 KB Output is correct
10 Correct 3451 ms 17044 KB Output is correct