Submission #788040

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
788040	2023-07-19T16:50:42 Z	khshg	Digital Circuit (IOI22_circuit)	C++17	50 / 100	3000 ms	21900 KB

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) {
	return ADD(A, MOD - B);
}

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, r);
	}
	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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Execution timed out	3061 ms	208 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #2
7.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	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	464 KB	Output is correct
8	Correct	1 ms	464 KB	Output is correct
9	Correct	1 ms	464 KB	Output is correct
10	Correct	1 ms	464 KB	Output is correct
11	Correct	1 ms	464 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Execution timed out	3061 ms	208 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	507 ms	5500 KB	Output is correct
2	Correct	704 ms	10664 KB	Output is correct
3	Correct	639 ms	10668 KB	Output is correct
4	Correct	735 ms	10744 KB	Output is correct

Subtask #5
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	507 ms	5500 KB	Output is correct
2	Correct	704 ms	10664 KB	Output is correct
3	Correct	639 ms	10668 KB	Output is correct
4	Correct	735 ms	10744 KB	Output is correct
5	Correct	610 ms	5536 KB	Output is correct
6	Correct	601 ms	10728 KB	Output is correct
7	Correct	912 ms	10832 KB	Output is correct
8	Correct	758 ms	10624 KB	Output is correct
9	Correct	272 ms	552 KB	Output is correct
10	Correct	677 ms	976 KB	Output is correct
11	Correct	611 ms	936 KB	Output is correct
12	Correct	496 ms	976 KB	Output is correct

Subtask #6
27.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	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	464 KB	Output is correct
8	Correct	1 ms	464 KB	Output is correct
9	Correct	1 ms	464 KB	Output is correct
10	Correct	1 ms	464 KB	Output is correct
11	Correct	1 ms	464 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	507 ms	5500 KB	Output is correct
14	Correct	704 ms	10664 KB	Output is correct
15	Correct	639 ms	10668 KB	Output is correct
16	Correct	735 ms	10744 KB	Output is correct
17	Correct	610 ms	5536 KB	Output is correct
18	Correct	601 ms	10728 KB	Output is correct
19	Correct	912 ms	10832 KB	Output is correct
20	Correct	758 ms	10624 KB	Output is correct
21	Correct	272 ms	552 KB	Output is correct
22	Correct	677 ms	976 KB	Output is correct
23	Correct	611 ms	936 KB	Output is correct
24	Correct	496 ms	976 KB	Output is correct
25	Correct	737 ms	16988 KB	Output is correct
26	Correct	742 ms	17204 KB	Output is correct
27	Correct	847 ms	17212 KB	Output is correct
28	Correct	609 ms	16980 KB	Output is correct
29	Correct	833 ms	21900 KB	Output is correct
30	Correct	688 ms	21668 KB	Output is correct

Subtask #7
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Execution timed out	3061 ms	208 KB	Time limit exceeded
3	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	Execution timed out	3061 ms	208 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Submission #788040

Compilation message