Submission #31661

#	Time	Username	Problem	Language	Result	Execution time	Memory
31661		antran2202	Relativnost (COCI15_relativnost)	C++14	42 / 140	239 ms	20776 KiB

relativnost

#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
#define whole(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define sqr(x) ((x)*(x))
#define pb push_back
#define mp make_pair
#define ins insert
#define maxn int (1e5 + 1)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
//----------------------------------------------------------
int n, x, y, c, q, mod = 1e4 + 7;
vector <short int> a, b;
struct Node
{
	vector <short int> f;
	unsigned short int l, r;
} T[maxn * 4];
void Merge (Node &res, Node L, Node R)
{
	fill (whole (res.f), 0);
	for (int i = 0; i <= c; ++i)
		for (int j = 0; j <= c; ++j)
		{
			int x = min (c, i + j);
			res.f[x] = (res.f[x] + L.f[i] * R.f[j]) % mod;
		}
}
void Build (int id)
{
	T[id].f.resize (c + 1, 0);
	if (T[id].l == T[id].r)
	{
		T[id].f[0] = b[T[id].l];
		T[id].f[1] = a[T[id].l];
		return;
	}
	T[id<<1].l = T[id].l, T[id<<1].r = (T[id].l + T[id].r) >> 1;
	T[id<<1|1].l = ((T[id].l + T[id].r) >> 1) + 1, T[id<<1|1].r = T[id].r;
	Build (id<<1);
	Build (id<<1|1);
	Merge (T[id], T[id<<1], T[id<<1|1]);
}
int pos;
void Update (int id)
{
	if (T[id].l > pos or pos > T[id].r) return;
	if (T[id].l == T[id].r)
	{
		T[id].f[0] = b[pos];
		T[id].f[1] = a[pos];
		return;
	}
	Update (id<<1);
	Update (id<<1|1);
	Merge (T[id], T[id<<1], T[id<<1|1]);
}
void Input ()
{
	cin >> n >> c;
	a.resize (n + 1);
	b.resize (n + 1);
	for (int i = 1; i <= n; ++i)
		cin >> x, a[i] = x % mod;
	for (int i = 1; i <= n; ++i)
		cin >> x, b[i] = x % mod;
	cin >> q;
}
void Solve ()
{
	T[1].l = 1, T[1].r = n;
	Build (1);
	for (;q;--q)
	{
		cin >> pos >> x >> y;
		a[pos] = x % mod, b[pos] = y % mod;
		Update (1);
		cout << T[1].f[c] << '\n';
	}
}
int main()
{
	//freopen ("relativnost.inp", "r", stdin);
	//freopen ("relativnost.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie (NULL);
	cout.tie (NULL);
	Input ();
	Solve ();
}

• Subtask 1: 42 / 140