oj.uz

Submission #874948

# Submission time Handle Problem Language Result Execution time Memory
874948 2023-11-18T07:58:47 Z serifefedartar Relativnost (COCI15_relativnost) C++17
140 / 140
 2570 ms 26348 KB 
#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 10007;
const ll LOGN = 20; 
const ll MAXN = 1e5 + 100;

int A[MAXN], B[MAXN], C;
struct Node {
	int taken[21];
	Node() {
		for (int i = 0; i < 21; i++)
			taken[i] = 0;
	}
};

Node sg[3*MAXN]; 
Node merge(Node a, Node b) {
	Node new_node;
	for (int i = 0; i <= C; i++) {
		for (int j = 0; j <= C; j++)
			new_node.taken[min(C, i + j)] = (new_node.taken[min(C, i + j)] + a.taken[i] * b.taken[j]) % MOD;
	}
	return new_node;
}

void init(int k, int a, int b) {
	if (a == b) {
		sg[k].taken[0] = B[a] % MOD;
		sg[k].taken[1] = A[a] % MOD;
		return ;
	}
	init(2*k, a, (a+b)/2);
	init(2*k+1, (a+b)/2+1, b);
	sg[k] = merge(sg[2*k], sg[2*k+1]);
}

void update(int k, int a, int b, int plc, pair<int,int> v) {
	if (b < plc || a > plc)
		return ;
	if (a == b) {
		sg[k].taken[0] = v.s % MOD;
		sg[k].taken[1] = v.f % MOD;
		return ;
	}
	update(2*k, a, (a+b)/2, plc, v);
	update(2*k+1, (a+b)/2+1, b, plc, v);
	sg[k] = merge(sg[2*k], sg[2*k+1]);
}

int main() {
	fast
	int N;
	cin >> N >> C;

	for (int i = 1; i <= N; i++)
		cin >> A[i];
	for (int i = 1; i <= N; i++)
		cin >> B[i];
	init(1, 1, N);

	int Q, P, a, b;
	cin >> Q;
	while (Q--) {
		cin >> P >> a >> b;
		update(1, 1, N, P, {a, b});
		cout << sg[1].taken[C] << "\n";
	}
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25180 KB Output is correct
2 Correct 12 ms 25180 KB Output is correct
3 Correct 21 ms 25236 KB Output is correct
4 Correct 323 ms 25800 KB Output is correct
5 Correct 1059 ms 26076 KB Output is correct
6 Correct 1614 ms 26348 KB Output is correct
7 Correct 705 ms 26008 KB Output is correct
8 Correct 352 ms 25936 KB Output is correct
9 Correct 676 ms 26328 KB Output is correct
10 Correct 2570 ms 26192 KB Output is correct