Submission #47718

#	Time	Username	Problem	Language	Result	Execution time	Memory
47718		tieunhi	Relativnost (COCI15_relativnost)	C++14	0 / 140	1 ms	528 KiB

relativnost

#include <bits/stdc++.h>
#define N 100005
#define mid (r + l)/2
#define L id*2
#define R id*2+1
#define mod 10007
using namespace std;

int n, C, a[N], b[N];

struct IntervalTree
{
	int t[N << 2][20];
	int s[N << 2];
	void build(int l, int r, int id)
	{
		if (l == r)
		{
			t[id][1] = a[l];
			t[id][0] = b[l];
			s[id] = a[l] + b[l];
			return;
		}
		build(l, mid, L);
		build(mid+1, r, R);
		for (int i = 0; i < C; i++)
			for (int j = 0; j < C; j++)
				if (i + j < C)
					t[id][i+j] = (t[id][i+j] + (t[L][i]*t[R][j]) % mod) % mod;
		s[id] = (s[L]*s[R]) % mod;
	}
	void update(int l, int r, int id, int x)
	{
		if (l > x || r < x) return;
		if (l == r)
		{
			t[id][1] = a[l];
			t[id][0] = b[l];
			s[id] = a[l] + b[l];
			return;
		}
		if (x <= mid) update(l, mid, L, x);
		else update(mid+1, r, R, x);
		for (int i = 0; i < C; i++) t[id][i] = 0;
		for (int i = 0; i < C; i++)
			for (int j = 0; j < C; j++)
				if (i + j < C)
					t[id][i+j] = (t[id][i+j] + (t[L][i]*t[R][j]) % mod) % mod;
		s[id] = (s[L]*s[R]) % mod;
	}
	int get()
	{
		int res = 0;
		for (int i = 0; i < C; i++)
			res = (res + t[1][i]);
		return (s[1] - res + mod) % mod;
	}
}t;
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//freopen("INP.TXT", "r", stdin);
	cin >> n >> C;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	t.build(1, n, 1);
	int numQuery; cin >> numQuery;
	while (numQuery--)
	{
		int pos, u, v; cin >> pos >> u >> v;
		a[pos] = u; b[pos] = v;
		t.update(1, n, 1, pos);
		cout <<t.get()<<'\n';
	}
}

• Subtask 1: 0 / 140