Submission #632761

#	Time	Username	Problem	Language	Result	Execution time	Memory
632761		rainboy	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1108 ms	26144 KiB

circuit

#include "circuit.h"
#include <vector>
#include <stdlib.h>

using namespace std;
typedef vector<int> vi;

const int N = 100000, M = 100000, N_ = (1 << 18), MD = 1000002022;	/* N_ = pow2(ceil(log2(N + M))) */

int *ej[N + M], eo[N + M];

void append(int i, int j) {
	int o = eo[i]++;
	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int st1[N_ * 2], st2[N_ * 2], sum[N_ * 2], h_, n, m, n_; char lz[N_];

void pul1(int i) {
	st1[i] = (long long) st1[i << 1 | 0] * st1[i << 1 | 1] % MD;
}

void build1(int *aa, int n) {
	for (int i = 0; i < n_; i++)
		st1[n_ + i] = i < n ? aa[i] : 1;
	for (int i = n_ - 1; i > 0; i--)
		pul1(i);
}

void update1(int i, int x) {
	i += n_;
	st1[i] = x;
	while (i > 1)
		pul1(i >>= 1);
}

void put2(int i) {
	st2[i] = (sum[i] - st2[i] + MD) % MD;
	if (i < n_)
		lz[i] ^= 1;
}

void pus2(int i) {
	if (lz[i])
		put2(i << 1 | 0), put2(i << 1 | 1), lz[i] = 0;
}

void pul2(int i) {
	if (!lz[i])
		st2[i] = (st2[i << 1 | 0] + st2[i << 1 | 1]) % MD;
}

void push2(int i) {
	for (int h = h_; h > 0; h--)
		pus2(i >> h);
}

void pull2(int i) {
	while (i > 1)
		pul2(i >>= 1);
}

void build2(vi aa, int *ww, int n) {
	for (int i = 0; i < n_; i++)
		if (i < n)
			sum[n_ + i] = ww[i], st2[n_ + i] = aa[i] == 1 ? ww[i] : 0;
		else
			sum[n_ + i] = 0, st2[n_ + i] = 0;
	for (int i = n_ - 1; i > 0; i--) {
		sum[i] = (sum[i << 1 | 0] + sum[i << 1 | 1]) % MD;
		pul2(i);
	}
}

void update2(int l, int r) {
	int l_ = l += n_, r_ = r += n_;
	push2(l_), push2(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put2(l++);
		if ((r & 1) == 0)
			put2(r--);
	}
	pull2(l_), pull2(r_);
}

int ww[M];

void dfs(int i) {
	if (i >= n)
		ww[i - n] = st1[1];
	else {
		update1(i, 1);
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			dfs(j);
		}
		update1(i, eo[i]);
	}
}

void init(int n1, int m_, vi pp, vi aa) {
	n = n1, m = m_;
	for (int i = 0; i < n + m; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (int i = 1; i < n + m; i++)
		append(pp[i], i);
	h_ = 0;
	while (1 << h_ < n + m)
		h_++;
	n_ = 1 << h_;
	build1(eo, n);
	dfs(0);
	build2(aa, ww, m);
}

int count_ways(int l, int r) {
	l -= n, r -= n;
	update2(l, r);
	return st2[1];
}

Compilation message (stderr)

circuit.cpp: In function 'void append(int, int)':
circuit.cpp:14:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11