oj.uz

Submission #1060304

# Submission time Handle Problem Language Result Execution time Memory
1060304 2024-08-15T12:50:26 Z DorostWef Digital Circuit (IOI22_circuit) C++17
4 / 100
 642 ms 27224 KB 
#include "circuit.h"

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target ("avx2")

using namespace std;
#define int long long
const int N = 200023, M = 1000002022;
int a[N], p[N];
int ans[N];
int st[N];
vector <int> g[N];
int pre[N], suf[N];
int x[N];

void predfs (int v) {
	int sz = (int)g[v].size();
	if (sz == 0) {
		st[v] = 1;
		return;
	}
	st[v] = sz;
	for (int u : g[v]) {
		predfs (u);
		st[v] = (st[v] * st[u]) % M;
	}
}

void dfs (int v) {
	int sz = (int)g[v].size();
	if (sz == 0) {
		return;
	}
	pre[0] = 1;
	suf[sz] = 1;
	for (int i = 0; i < sz; i++) {
		int u = g[v][i];
		pre[i + 1] = (pre[i] * st[u]) % M;
	}
	for (int i = sz - 1; i >= 0; i--) {
		int u = g[v][i];
		suf[i] = (suf[i + 1] * st[u]) % M;
	}
	for (int i = 0; i < sz; i++) {
		int u = g[v][i];
		ans[u] = (ans[v] * ((pre[i] * suf[i + 1]) % M) % M);
	}
	for (int i = 0; i < sz; i++) {
		int u = g[v][i];
		dfs (u);
	}
}

int m, n;

const int SegN = (1 << 19);
int seg[SegN], sum[SegN];
bool lz[SegN];

void build (int v = 1, int tl = 0, int tr = N - 1) {
	lz[v] = false;
	if (tl == tr) {
		seg[v] = a[tl] * p[tl];
		sum[v] = p[tl];
	} else {
		int mid = (tl + tr) >> 1;
		build (v << 1, tl, mid);
		build (v << 1 | 1, mid + 1, tr);
		seg[v] = seg[v << 1 | 1] + seg[v << 1];
		sum[v] = sum[v << 1 | 1] + sum[v << 1];
	}
}

void shift (int v) {
	if (lz[v]) {
		seg[v << 1] = sum[v << 1] - seg[v << 1];
		seg[v << 1 | 1] = sum[v << 1 | 1] - seg[v << 1 | 1];
		lz[v << 1] ^= 1;
		lz[v << 1 | 1] ^= 1;
	}
}

void upd (int l, int r, int v = 1, int tl = 0, int tr = N - 1) {
	if (l > tr || tl > r)
		return;
	if (l <= tl && tr <= r) {
		seg[v] = sum[v] - seg[v];
		lz[v] ^= 1;
		return;
	}
	shift (v);
	int mid = (tl + tr) >> 1;
	upd (l, r, v << 1, tl, mid);
	upd (l, r, v << 1 | 1, mid + 1, tr);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
	n = N;
	for (int i = 0; i < N + M; i++) {
		g[P[i]].push_back(i);
	}
	m = M;
	for (int i = 0; i < M; i++)
		a[i] = A[i];
	predfs (0);
	ans[0] = 1;
	dfs (0);
	for (int i = 0; i < M; i++)
		p[i] = ans[i + N];
	build();
}

int32_t count_ways(int32_t L, int32_t R) {
	L -= n;
	R -= n;
	upd (L, R);
	return seg[1] % M;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23128 KB Output is correct
2 Correct 4 ms 23128 KB Output is correct
3 Incorrect 4 ms 23216 KB 5th lines differ - on the 1st token, expected: '481', found: '476'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23096 KB Output is correct
2 Correct 3 ms 23056 KB Output is correct
3 Incorrect 4 ms 23128 KB 5th lines differ - on the 1st token, expected: '70832346', found: '964670064'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23128 KB Output is correct
2 Correct 4 ms 23128 KB Output is correct
3 Incorrect 4 ms 23216 KB 5th lines differ - on the 1st token, expected: '481', found: '476'
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 25176 KB Output is correct
2 Correct 633 ms 27224 KB Output is correct
3 Correct 642 ms 27224 KB Output is correct
4 Correct 631 ms 27216 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 25176 KB Output is correct
2 Correct 633 ms 27224 KB Output is correct
3 Correct 642 ms 27224 KB Output is correct
4 Correct 631 ms 27216 KB Output is correct
5 Incorrect 486 ms 25068 KB 4th lines differ - on the 1st token, expected: '17023698', found: '766803418'
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23096 KB Output is correct
2 Correct 3 ms 23056 KB Output is correct
3 Incorrect 4 ms 23128 KB 5th lines differ - on the 1st token, expected: '70832346', found: '964670064'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23128 KB Output is correct
2 Correct 4 ms 23128 KB Output is correct
3 Incorrect 4 ms 23216 KB 5th lines differ - on the 1st token, expected: '481', found: '476'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23128 KB Output is correct
2 Correct 4 ms 23128 KB Output is correct
3 Incorrect 4 ms 23216 KB 5th lines differ - on the 1st token, expected: '481', found: '476'
4 Halted 0 ms 0 KB -