Submission #736434

#	Time	Username	Problem	Language	Result	Execution time	Memory
736434		jk410	Digital Circuit (IOI22_circuit)	C++17	0 / 100	599 ms	2020 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000002022;
ll pow2[100000];
struct node {
	int sz;
	ll val;
};
node operator+(const node& a, const node& b) {
	node ret;
	ret.sz = a.sz + b.sz + 1;
	ret.val = a.val * b.val % MOD * 2 % MOD;
	ret.val = (ret.val + (pow2[a.sz] - a.val + MOD) % MOD * b.val % MOD) % MOD;
	ret.val = (ret.val + (pow2[b.sz] - b.val + MOD) % MOD * a.val % MOD) % MOD;
	return ret;
}

int N,M;

bool lazy[200000];
node tree[200000];

void propagate(int l, int r, int n) {
	if (!lazy[n])
		return;
	tree[n].val = (pow2[tree[n].sz] - tree[n].val + MOD) % MOD;
	if (l != r) {
		int m = (l + r) >> 1;
		lazy[n << 1] = !lazy[n << 1];
		lazy[n << 1 | 1] = !lazy[n << 1 | 1];
	}
	lazy[n] = false;
}

node update(int lx, int rx, int l, int r, int n) {
	propagate(l, r, n);
	if (r < lx || rx < l)
		return tree[n];
	if (lx <= l && r <= rx) {
		lazy[n] = !lazy[n];
		propagate(l, r, n);
		return tree[n];
	}
	int m = (l + r) >> 1;
	return tree[n] = update(lx, rx, l, m, n << 1) + update(lx, rx, m + 1, r, n << 1 | 1);
}

void init(int _n, int m, vector<int> _p, vector<int> a) {
	N = _n;
	pow2[0] = 1;
	for (int i = 1; i <= N; i++)
		pow2[i] = pow2[i - 1] * 2 % MOD;
	for (int i = 0; i < M; i++) {
		if (a[i])
			update(i, i, 0, N, 1);
	}
}

int count_ways(int l, int r) {
	update(l - N, r - N, 0, N, 1);
	propagate(0, N, 1);
	return tree[1].val;
}

Compilation message (stderr)

circuit.cpp: In function 'void propagate(int, int, int)':
circuit.cpp:30:7: warning: unused variable 'm' [-Wunused-variable]
   30 |   int m = (l + r) >> 1;
      |       ^

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