oj.uz

Submission #98672

# Submission time Handle Problem Language Result Execution time Memory
98672 2019-02-25T03:35:33 Z IOrtroiii Relativnost (COCI15_relativnost) C++14
0 / 140
 50 ms 33792 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 100005;
const int C = 22;
const int mod = 10007;

int n, c;

struct Info {
	int d[C];
	Info() {
		memset(d, 0, sizeof d);
	}
	void upd(int a,int b) {
		d[0] = b % mod;
		d[1] = a % mod;
	}
};

int a[N], b[N];
Info t[N << 2];

void Merge(Info &v, Info lv, Info rv) {
	for (int i = 0; i <= c; ++i) {
		v.d[i] = 0;
	}
	for (int i = 0; i <= c; ++i) {
		for (int j = 0; j <= c; ++j) {
			(v.d[min(i + j, c)] += (ll) (lv.d[i] * rv.d[j])) %= mod;
		}
	}
}

void build(int v,int l,int r) {
	if (l == r) {
		t[v].upd(a[l], b[l]);
		return;
	}
	int md = (l + r) >> 1;
	build(v << 1, l, md);
	build(v << 1 | 1, md + 1, r);
	Merge(t[v], t[v << 1], t[v << 1 | 1]);
}

void upd(int v,int l,int r,int p,int a,int b) {
	if (l == r) {
		t[v].upd(a, b);
		return;
	}
	int md = (l + r) >> 1;
	if (p <= md) {
		upd(v << 1, l, md, p, a, b);
	} else {
		upd(v << 1 | 1, md + 1, r, p, a, b);
	}
	Merge(t[v], t[v << 1], t[v << 1 | 1]);
} 

int main() {
	ios_base::sync_with_stdio(false);
	
	cin >> n >> c;
	
	for (int i = 1; i <= n; ++i) {
		cin >> a[i]; a[i] %= mod;
	} 
	
	for (int i = 1; i <= n; ++i) {
		cin >> b[i]; b[i] %= mod;
	}
	
	build(1, 1, n);
	int q;
	
	cin >> q;
	while (q--) {
		int p, ap, bp;
		
		cin >> p >> ap >> bp;
		ap %= mod, bp %= mod;
		upd(1, 1, n, p, ap, bp);
		cout << t[1].d[c] << '\n';
	}
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 41 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 38 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 41 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 50 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 39 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 43 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 40 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 47 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 45 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)