oj.uz

Submission #98626

# Submission time Handle Problem Language Result Execution time Memory
98626 2019-02-25T02:08:07 Z ToMo01 Relativnost (COCI15_relativnost) C++17
140 / 140
 3540 ms 20008 KB 
/*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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 17536 KB Output is correct
2 Correct 34 ms 17536 KB Output is correct
3 Correct 41 ms 17536 KB Output is correct
4 Correct 517 ms 18948 KB Output is correct
5 Correct 1552 ms 20008 KB Output is correct
6 Correct 2181 ms 19508 KB Output is correct
7 Correct 1022 ms 19072 KB Output is correct
8 Correct 588 ms 19100 KB Output is correct
9 Correct 1070 ms 19412 KB Output is correct
10 Correct 3540 ms 19276 KB Output is correct