Submission #788029

#	Time	Username	Problem	Language	Result	Execution time	Memory
788029		khshg	Digital Circuit (IOI22_circuit)	C++17	4 / 100	3071 ms	10664 KiB

circuit

#include"circuit.h"
#include<bits/stdc++.h>
using namespace std;

const long long MOD =  1000002022;

long long MUL(long long A, long long B) {
	return A * B % MOD;
}

long long ADD(long long A, long long B) {
	A += B;
	if(A >= MOD) A -= MOD;
	return A;
}

long long SUB(long long A, long long B) {
	A -= B;
	if(A < 0) A += MOD;
	return A;
}

int N, M;
vector<vector<int>> ch;
vector<int> par, stat;
vector<long long> sz, val;
long long ans;

void dfs(int s) {
	if(ch[s].empty()) {
		sz[s] = 1LL;
		return;
	}
	sz[s] = 2LL;
	for(auto& u : ch[s]) {
		dfs(u);
		sz[s] = MUL(sz[s], sz[u]);
	}
}

void ass_val(int s, long long v) {
	if(ch[s].empty()) { val[s - N] = v; return; }
	ass_val(ch[s][0], MUL(v, sz[ch[s][1]]));
	ass_val(ch[s][1], MUL(v, sz[ch[s][0]]));
}

const int maxn = 100000;
bool lazy[4 * maxn];
long long sum[4 * maxn], st[4 * maxn];

void build(int v, int tl, int tr) {
	if(tl == tr) {
		sum[v] = val[tl];
		if(stat[tr]) st[v] = sum[v];
		return;
	}
	int tm =(tl + tr) / 2;
	build(2 * v + 1, tl, tm);
	build(2 * v + 2, tm + 1, tr);
	sum[v] = ADD(sum[2 * v + 1], sum[2 * v + 2]);
	st[v] = ADD(st[2 * v + 1], st[2 * v + 2]);
}

void update(int v, int tl, int tr, int l, int r) {
	if(tl == l && tr == r) {
		lazy[v] ^= true;
		st[v] = SUB(sum[v], st[v]);
		return;
	}
	int tm = (tl + tr) / 2;
	if(lazy[v]) {
		lazy[v] = false;
		lazy[2 * v + 1] ^= true;
		st[2 * v + 1] = SUB(sum[2 * v + 1], st[2 * v + 1]);
		lazy[2 * v + 2] ^= true;
		st[2 * v + 2] = SUB(sum[2 * v + 2], st[2 * v + 2]);
	}
	if(r <= tm) {
		update(2 * v + 1, tl, tm, l, r);
	} else if(l > tm) {
		update(2 * v + 2, tm + 1, tr, l, r);
	} else {
		update(2 * v + 1, tl, tm, l, tm);
		update(2 * v + 2, tm + 1, tr, tm + 1, tr);
	}
	st[v] = ADD(st[2 * v + 1], st[2 * v + 2]);
}

void init(int _N, int _M, vector<int> P, vector<int> A) {
	N = _N; M = _M;
	swap(P, par);
	swap(A, stat);
	val.resize(M);
	ch.resize(N + M);
	sz.resize(N + M);
	for(int i = 1; i < N + M; ++i) {
		ch[par[i]].push_back(i);
	}
	dfs(0);
	ass_val(0, 1LL);
	build(0, 0, M - 1);
}

int count_ways(int L, int R) {
	L -= N; R -= N;
	update(0, 0, M - 1, L, R);
	return st[0];
}

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