Submission #98626

#	Time	Username	Problem	Language	Result	Execution time	Memory
98626		ToMo01	Relativnost (COCI15_relativnost)	C++17	140 / 140	3540 ms	20008 KiB

relativnost

/*input
4 2
1 2 3 4
1 2 3 4
1
4 1 1
*/
#include <bits/stdc++.h>
using namespace std;

int read() {
	int number = 0, c = getchar();
	for(; !(c > 47 && c < 58); c = getchar());
	for(; (c > 47 && c < 58); c = getchar()) number = (number << 3) + (number << 1) + c - 48;
	return number;
}

const int N = 100000, Mod = 10007;
int a[N], b[N], n, c;

struct Node {
	int Ans[22];
	Node(int w = 0, int b = 0) {
		memset(Ans, 0, sizeof Ans);
		Ans[0] = w % Mod, Ans[1] = b % Mod;
	}
} tree[N << 1];


Node Merge(Node a, Node b) {
	Node cur = Node();	
	for(int i = 0; i <= c + 1; ++ i) for(int j = 0; j <= c + 1; ++ j) {
		int nxt = min(c + 1, i + j);
		cur.Ans[nxt] = (cur.Ans[nxt] + a.Ans[i] * b.Ans[j]) % Mod;
	}
	return cur;
}

void Update(int pos, Node val) {
	for(tree[pos += n] = val; pos >>= 1;)
		 tree[pos] = Merge(tree[pos << 1], tree[pos << 1 | 1]);
}

int main(){
	n = read(), c = read();
	for(int i = 0; i < n; a[i ++] = read());
	for(int i = 0; i < n; b[i ++] = read());
	for(int i = 0; i < n; ++ i) tree[i + n] = Node(b[i], a[i]);
	for(int i = n - 1; i > 0; -- i) tree[i] = Merge(tree[i << 1], tree[i << 1 | 1]);

	for(int q = read(); q -- > 0;) {
		int pos = read() - 1, b = read(), w = read();
		Update(pos, Node(w, b)), printf("%d\n", (tree[1].Ans[c] + tree[1].Ans[c + 1]) % Mod);
	}
}

• Subtask 1: 140 / 140