Submission #31659

#	Time	Username	Problem	Language	Result	Execution time	Memory
31659		antran2202	Relativnost (COCI15_relativnost)	C++14	0 / 140	46 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, k, m, c, q;
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)
		{
			res.f[min (c, i + j)] += L.f[i] * R.f[j];
		}
}
void Build (int id)
{
	int l = T[id].l, r = T[id].r, mid = (l + r) >> 1;
	T[id].f.resize (c + 1, 0);
	if (l == r)
	{
		T[id].f[0] = b[l];
		T[id].f[1] = a[l];
		return;
	}
	T[id<<1].l = l, T[id<<1].r = mid;
	T[id<<1|1].l = mid+1, T[id<<1|1].r = r;
	Build (id<<1);
	Build (id<<1|1);
	Merge (T[id], T[id<<1], T[id<<1|1]);
}
int pos;
void Update (int id)
{
	int l = T[id].l, r = T[id].r;
	if (l > pos or pos > r) return;
	if (l == r)
	{
		T[id].f[0] = b[l];
		T[id].f[1] = a[l];
		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 >> a[i];
	for (int i = 1; i <= n; ++i)
		cin >> b[i];
	cin >> q;
}
void Solve ()
{
	T[1].l = 1, T[1].r = n;
	Build (1);
	for (;q;--q)
	{
		cin >> pos;
		cin >> a[pos] >> b[pos];
		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: 0 / 140