제출 #1172762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172762		nuutsnoynton	Relativnost (COCI15_relativnost)	C++20	140 / 140	2235 ms	25792 KiB

relativnost

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 2e5 + 2;
const ll mod = 1e4 + 7;
ll ST[23][4 * N] = {0}, a[N], b[N], C;

void Build(ll p, ll lo, ll hi) {
	if ( lo == hi) {
		ST[0][p] = b[lo];
		ST[1][p] = a[lo];
		return ;
	}
	ll j, r,s, mid = (lo + hi)/2;
	Build(2 * p, lo, mid);
	Build(2 * p + 1, mid + 1, hi);
	for (j = 0; j <= C; j ++) ST[j][p]= 0;
	for (j = 0; j <= C; j ++) {
		for ( r = 0; r <= C; r ++) {
			s = min(r + j, C);
			ST[s][p] = ST[s][p] + (ST[j][2 * p] * ST[r][2 * p + 1]); 
			ST[s][p] %= mod;
		}
	}
	return ;
}

void Update(ll p, ll lo, ll hi, ll x) {
	if ( lo == hi) {
		ST[0][p] = b[lo];
		ST[1][p] = a[lo];
		return ;
	}
	ll j, r, s, mid = (lo + hi)/2;
	if ( x <= mid) Update(2 * p, lo, mid, x);
	else Update(2 * p + 1, mid +1, hi, x);
	
	for (j = 0; j <= C; j ++) ST[j][p]= 0;
	for (j = 0; j <= C; j ++) {
		for ( r = 0; r <= C; r ++) {
			s = min(r + j, C);
			ST[s][p] = ST[s][p] + (ST[j][2 * p] * ST[r][2 * p + 1]); 
			ST[s][p] %= mod;
		}
	}
	return ;
}

int main() {
	ll n, m, r, x, y, i, j, ans, t, ind;

	cin >> n >> C;
	
	for (i = 1; i <= n; i ++) cin >> a[i];
	for (i = 1; i <= n; i ++) cin >> b[i];
	
	cin >> t;
	Build(1, 1, n);
	while ( t --) {
		cin >> ind >> x >> y;
		a[ind] = x;
		b[ind] = y;
		Update(1, 1, n, ind);
		
		cout << ST[C][1] << endl;
		
	}
}

• Subtask 1: 140 / 140