Submission #788029

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
788029	2023-07-19T16:40:54 Z	khshg	Digital Circuit (IOI22_circuit)	C++17	4 / 100	3000 ms	10664 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) {
	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.0

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

Subtask #2
0 / 7.0

#	Verdict	Memory	Grader output
1	Correct	208 KB	Output is correct
2	Incorrect	336 KB	1st lines differ - on the 1st token, expected: '52130940', found: '474414066'
3	Halted	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Execution timed out	3071 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	481 ms	5508 KB	Output is correct
2	Correct	657 ms	10664 KB	Output is correct
3	Correct	757 ms	10664 KB	Output is correct
4	Correct	682 ms	10660 KB	Output is correct

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	481 ms	5508 KB	Output is correct
2	Correct	657 ms	10664 KB	Output is correct
3	Correct	757 ms	10664 KB	Output is correct
4	Correct	682 ms	10660 KB	Output is correct
5	Incorrect	544 ms	5540 KB	1st lines differ - on the 1st token, expected: '105182172', found: '748994286'
6	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	Verdict	Memory	Grader output
1	Correct	208 KB	Output is correct
2	Incorrect	336 KB	1st lines differ - on the 1st token, expected: '52130940', found: '474414066'
3	Halted	0 KB	-

Subtask #7
0 / 28.0

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

Submission #788029

Compilation message