oj.uz

Submission #31660

# Submission time Handle Problem Language Result Execution time Memory
31660 2017-08-30T14:39:34 Z antran2202 Relativnost (COCI15_relativnost) C++14
42 / 140
 253 ms 20776 KB 
#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)
{
	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 >> 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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14680 KB Output is correct
2 Correct 33 ms 14680 KB Output is correct
3 Correct 46 ms 14680 KB Output is correct
4 Runtime error 103 ms 18116 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 69 ms 16864 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 116 ms 17416 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 253 ms 20776 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 46 ms 16624 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 26 ms 15504 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 43 ms 15488 KB Execution killed because of forbidden syscall writev (20)