oj.uz

답안 #788040

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
788040 2023-07-19T16:50:42 Z khshg 디지털 회로 (IOI22_circuit) C++17
50 / 100
 3000 ms 21900 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -