oj.uz

Submission #98629

# Submission time Handle Problem Language Result Execution time Memory
98629 2019-02-25T02:10:22 Z ToMo01 Relativnost (COCI15_relativnost) C++14
140 / 140
 3430 ms 18808 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(const Node &a, const 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 28 ms 17536 KB Output is correct
2 Correct 32 ms 17536 KB Output is correct
3 Correct 38 ms 17536 KB Output is correct
4 Correct 530 ms 18328 KB Output is correct
5 Correct 1488 ms 18808 KB Output is correct
6 Correct 2237 ms 18808 KB Output is correct
7 Correct 1018 ms 18360 KB Output is correct
8 Correct 602 ms 18576 KB Output is correct
9 Correct 996 ms 18680 KB Output is correct
10 Correct 3430 ms 18692 KB Output is correct