oj.uz

Submission #47718

# Submission time Handle Problem Language Result Execution time Memory
47718 2018-05-06T16:52:55 Z tieunhi Relativnost (COCI15_relativnost) C++14
0 / 140
 1 ms 528 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1 ms 224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 1 ms 272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 1 ms 328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 1 ms 332 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 1 ms 372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 1 ms 400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 1 ms 528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 1 ms 528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 1 ms 528 KB Execution killed with signal 11 (could be triggered by violating memory limits)