oj.uz

답안 #1020026

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1020026 2024-07-11T13:00:24 Z vako_p Relativnost (COCI15_relativnost) C++14
0 / 140
 1507 ms 55568 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 1e5 + 5;
ll n,C,c[mxN],c1[mxN],a[mxN],b[mxN],q,mod = 10007,ans,sz;
vector<vector<ll>> v;
vector<ll> v1;

struct segtree{	
	void init(){	
		sz = 1;
		while(sz < mxN) sz *= 2;
		v.assign(2 * sz, vector<ll>(20));
		v1.assign(2 * sz, 1LL);
		for(int i = 0; i < 2 * sz; i++) v[i][0] = 1;
	}
	
	void set(ll i, ll x, ll l, ll r){
		if(r - l == 1){
			v[x][0] = b[i];
			v[x][1] = a[i];
			v1[x] = (a[i] + b[i]) % mod;
			return;
		}	
		ll mid = l + (r - l) / 2;
		if(i < mid) set(i, 2 * x + 1, l, mid);
		else set(i, 2 * x + 2, mid, r);
		for(int j = 0; j < C; j++) v[x][j] = 0;
		for(int j = 0; j < C; j++) for(int k = 0; k + j < C; k++) 
			v[x][k + j] = (v[x][j + k] + v[2 * x + 1][j] * v[2 * x + 2][k]) % mod;	
		v1[x] = v1[2 * x + 1] *  v1[2 * x + 2] % mod;
	}
	
	void set(ll i){
		set(i, 0, 0, sz);
	}
	
//	void find(ll l, ll r, ll x, ll lx, ll rx){
//		if(lx >= r or rx <= l) return;
//		if(lx >= l and rx <= r){
//			for(int i = 0; i < C; i++){
//				for(int j = 0; j + i < C; j++) c1[i + j] = (c1[i + j] + c[i] * v[x][j]) % mod;
//				c[i] = c1[i];
//			}
//			ans *= v1[x];
//			return;
//		}
//		ll mid = lx + (rx - lx) / 2;
//		find(l, r, 2 * x + 1, lx, mid);
//		find(l, r, 2 * x + 2, mid, rx);
//	}
//	
//	void find(ll l, ll r){
//		for(int i = 0; i < C; i++){
//			c[i] = c1[i] = 0;  
//		}
//		c[0] = 1;
//		ans = 1;
//		find(l, r, 0, 0, sz);
//	}
};

segtree s;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> C;
	s.init();
	for(int i = 0; i < n; i++){
		cin >> a[i];
		a[i] %= mod;
	}
	for(int i = 0; i < n; i++){
		cin >> b[i];
		b[i] %= mod;
		s.set(i);
	}
	cin >> q;
	while(q--){
		ll i,a1,b1;
		cin >> i >> a1 >> b1;
		i--;
		a[i] = a1 % mod;
		b[i] = b1 % mod;
		s.set(i);
		ans = v1[0];
		for(int i1 = 0; i1 < C; i1++){
			ans = (ans - v[0][i1] + mod) % mod;
		}
		cout << ans << '\n';
	}
}

Subtask #1
0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 36 ms 53852 KB Memory limit exceeded
2 Runtime error 48 ms 53704 KB Memory limit exceeded
3 Runtime error 48 ms 53584 KB Memory limit exceeded
4 Runtime error 230 ms 54868 KB Memory limit exceeded
5 Runtime error 752 ms 55568 KB Memory limit exceeded
6 Runtime error 1186 ms 55372 KB Memory limit exceeded
7 Runtime error 517 ms 54840 KB Memory limit exceeded
8 Runtime error 319 ms 55368 KB Memory limit exceeded
9 Runtime error 481 ms 55264 KB Memory limit exceeded
10 Runtime error 1507 ms 55492 KB Memory limit exceeded