oj.uz

답안 #31665

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31665 2017-08-30T15:19:19 Z antran2202 Relativnost (COCI15_relativnost) C++14
42 / 140
 129 ms 8628 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];
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.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 5304 KB Output is correct
2 Correct 26 ms 5304 KB Output is correct
3 Correct 49 ms 5304 KB Output is correct
4 Runtime error 33 ms 7156 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 69 ms 7488 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 129 ms 8040 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 79 ms 8628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 56 ms 7248 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 33 ms 6128 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 46 ms 6112 KB Execution killed because of forbidden syscall writev (20)