oj.uz

Submission #807528

# Submission time Handle Problem Language Result Execution time Memory
807528 2023-08-04T19:00:15 Z alex_2008 Digital Circuit (IOI22_circuit) C++17
16 / 100
 851 ms 4688 KB 
#include "circuit.h"
#include <cmath>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;
int NN, MM;
const int N = 2e5 + 10, P = 1000002022;
int p[N];
int lazy[4 * N];
int a[N];
pair <ll, ll> tree[4 * N];
bool ch = true;
void pushh(int v, int tl, int tr) {
	if (lazy[v]) {
		lazy[v] = 0;
		if (tl != tr) {
			lazy[2 * v] = (lazy[2 * v] + 1) % 2;
			lazy[2 * v + 1] = (lazy[2 * v + 1] + 1) % 2;
			swap(tree[2 * v].first, tree[2 * v].second);
			swap(tree[2 * v + 1].first, tree[2 * v + 1].second);
		}
	}
}
void build_tree(int v, int tl, int tr) {
	if (tl == tr) {
		if (a[tl] == 1) tree[v] = { 1, 0 };
		else tree[v] = { 0, 1 };
	}
	else {
		int tm = (tl + tr) / 2;
		build_tree(2 * v, tl, tm);
		build_tree(2 * v + 1, tm + 1, tr);
		ll a = tree[2 * v].first, b = tree[2 * v].second, c = tree[2 * v + 1].first, d = tree[2 * v + 1].second;
		tree[v].first = 2 * a * c + a * d + b * c;
		tree[v].second = 2 * b * d + a * d + b * c;
		tree[v].first %= P;
		tree[v].second %= P;
	}
}
void update(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l) return;
	if (tl >= l && tr <= r) {
		lazy[v] = (lazy[v] + 1) % 2;
		swap(tree[v].first, tree[v].second);
		return;
	}
	pushh(v, tl, tr);
	int tm = (tl + tr) / 2;
	update(2 * v, tl, tm, l, r);
	update(2 * v + 1, tm + 1, tr, l, r);
	ll a = tree[2 * v].first, b = tree[2 * v].second, c = tree[2 * v + 1].first, d = tree[2 * v + 1].second;
	tree[v].first = 2 * a * c + a * d + b * c;
	tree[v].second = 2 * b * d + a * d + b * c;
	tree[v].first %= P;
	tree[v].second %= P;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
	NN = N, MM = M;
	for (int i = 0; i < N + M - 1; i++) {
		p[i] = P[i];
		if (i > 0 && p[i] != (i - 1) / 2) ch = false;
	}
	for (int i = 0; i < M; i++) {
		a[i] = A[i];
	}
	if (M != N + 1) ch = false;
	int u = log2(M);
	if ((1 << u) != M) ch = false;
	build_tree(1, 0, M - 1);
}
int count_ways(int L, int R) {
	update(1, 0, MM - 1, L - NN, R - NN);
	return tree[1].first;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '509', found: '159879670'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '518808754'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '509', found: '159879670'
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 2496 KB Output is correct
2 Correct 711 ms 4588 KB Output is correct
3 Correct 572 ms 4660 KB Output is correct
4 Correct 748 ms 4664 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 2496 KB Output is correct
2 Correct 711 ms 4588 KB Output is correct
3 Correct 572 ms 4660 KB Output is correct
4 Correct 748 ms 4664 KB Output is correct
5 Correct 446 ms 2492 KB Output is correct
6 Correct 741 ms 4652 KB Output is correct
7 Correct 851 ms 4668 KB Output is correct
8 Correct 717 ms 4688 KB Output is correct
9 Correct 384 ms 464 KB Output is correct
10 Correct 634 ms 592 KB Output is correct
11 Correct 820 ms 592 KB Output is correct
12 Correct 663 ms 592 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '518808754'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '509', found: '159879670'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '509', found: '159879670'
4 Halted 0 ms 0 KB -