제출 #648721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
648721		Adominator	Relativnost (COCI15_relativnost)	C++17	140 / 140	3451 ms	17044 KiB

relativnost

#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 / 140