oj.uz

Submission #800661

# Submission time Handle Problem Language Result Execution time Memory
800661 2023-08-01T17:35:48 Z dxz05 Digital Circuit (IOI22_circuit) C++17
52 / 100
 799 ms 24916 KB 
#include "circuit.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int MaxN = 200005;
const int MOD = 1e9 + 2022;

int N, M;
vector<int> A;

int contribution[MaxN];

struct node{
	int sum;
	int sum2;
	bool flag;
	
	node(){
		sum = sum2 = 0;
		flag = false;
	};
};

node tree[4 * MaxN];

void flip(int v){
	swap(tree[v].sum, tree[v].sum2);
	tree[v].flag ^= 1;
}

void push(int v, int tl, int tr){
	if (tl == tr || !tree[v].flag) return;
	flip(v << 1);
	flip(v << 1 | 1);
	tree[v].flag = false;
}

void build(int v, int tl, int tr){
	if (tl == tr){
		tree[v].sum = A[tl - N] * contribution[tl];
		tree[v].sum2 = (!A[tl - N]) * contribution[tl];
		return;
	}
	int tm = (tl + tr) >> 1;
	build(v << 1, tl, tm);
	build(v << 1 | 1, tm + 1, tr);
	
	tree[v].sum = (tree[v << 1].sum + tree[v << 1 | 1].sum) % MOD;
	tree[v].sum2 = (tree[v << 1].sum2 + tree[v << 1 | 1].sum2) % MOD;
}

void update(int v, int tl, int tr, int l, int r){
	push(v, tl, tr);
	if (l <= tl && tr <= r){
		flip(v);
		return;
	}
	if (tl > r || tr < l) return;
	int tm = (tl + tr) >> 1;
	update(v << 1, tl, tm, l, r);
	update(v << 1 | 1, tm + 1, tr, l, r);
	
	tree[v].sum = (tree[v << 1].sum + tree[v << 1 | 1].sum) % MOD;
	tree[v].sum2 = (tree[v << 1].sum2 + tree[v << 1 | 1].sum2) % MOD;
}

void update(int l, int r){
	update(1, N, N + M - 1, l, r);
}

int get(){
	return tree[1].sum;
}

vector<int> g[MaxN];
 
int dep[MaxN];

void dfs(int v, int p){
	for (int u : g[v]){
		if (u != p){
			dep[u] = dep[v] + 1;
			dfs(u, v);
		}
	}		
}

void init(int _N, int _M, vector<int> P, vector<int> _A) {
    N = _N, M = _M, A = _A;
    for (int i = 1; i < N + M; i++){
        g[P[i]].push_back(i);
    }
    dfs(0, -1);
    
    vector<int> pw(N + 1, 1);
    for (int i = 1; i <= N; i++) pw[i] = pw[i - 1] * 2 % MOD;
    
    for (int i = N; i < N + M; i++){
		contribution[i] = pw[N - dep[i]];
	}
    
    build(1, N, N + M - 1);
}
 
int count_ways(int L, int R) {
    update(L, R);
    return get();
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14288 KB Output is correct
2 Correct 8 ms 14288 KB Output is correct
3 Correct 6 ms 14416 KB Output is correct
4 Correct 6 ms 14416 KB Output is correct
5 Correct 6 ms 14416 KB Output is correct
6 Correct 7 ms 14408 KB Output is correct
7 Correct 6 ms 14416 KB Output is correct
8 Correct 7 ms 14368 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14288 KB Output is correct
2 Correct 7 ms 14416 KB Output is correct
3 Correct 8 ms 14372 KB Output is correct
4 Correct 6 ms 14416 KB Output is correct
5 Correct 7 ms 14324 KB Output is correct
6 Correct 8 ms 14416 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 7 ms 14380 KB Output is correct
9 Correct 8 ms 14412 KB Output is correct
10 Correct 6 ms 14416 KB Output is correct
11 Correct 6 ms 14416 KB Output is correct
12 Correct 6 ms 14416 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14288 KB Output is correct
2 Correct 8 ms 14288 KB Output is correct
3 Correct 6 ms 14416 KB Output is correct
4 Correct 6 ms 14416 KB Output is correct
5 Correct 6 ms 14416 KB Output is correct
6 Correct 7 ms 14408 KB Output is correct
7 Correct 6 ms 14416 KB Output is correct
8 Correct 7 ms 14368 KB Output is correct
9 Correct 7 ms 14288 KB Output is correct
10 Correct 7 ms 14416 KB Output is correct
11 Correct 8 ms 14372 KB Output is correct
12 Correct 6 ms 14416 KB Output is correct
13 Correct 7 ms 14324 KB Output is correct
14 Correct 8 ms 14416 KB Output is correct
15 Correct 8 ms 14416 KB Output is correct
16 Correct 7 ms 14380 KB Output is correct
17 Correct 8 ms 14412 KB Output is correct
18 Correct 6 ms 14416 KB Output is correct
19 Correct 6 ms 14416 KB Output is correct
20 Correct 6 ms 14416 KB Output is correct
21 Incorrect 6 ms 14416 KB 1st lines differ - on the 1st token, expected: '759476520', found: '833967706'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 16844 KB Output is correct
2 Correct 662 ms 19260 KB Output is correct
3 Correct 688 ms 19256 KB Output is correct
4 Correct 677 ms 19256 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 16844 KB Output is correct
2 Correct 662 ms 19260 KB Output is correct
3 Correct 688 ms 19256 KB Output is correct
4 Correct 677 ms 19256 KB Output is correct
5 Correct 584 ms 16848 KB Output is correct
6 Correct 713 ms 19256 KB Output is correct
7 Correct 738 ms 19256 KB Output is correct
8 Correct 647 ms 19264 KB Output is correct
9 Correct 367 ms 14544 KB Output is correct
10 Correct 649 ms 14632 KB Output is correct
11 Correct 624 ms 14660 KB Output is correct
12 Correct 619 ms 14672 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14288 KB Output is correct
2 Correct 7 ms 14416 KB Output is correct
3 Correct 8 ms 14372 KB Output is correct
4 Correct 6 ms 14416 KB Output is correct
5 Correct 7 ms 14324 KB Output is correct
6 Correct 8 ms 14416 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 7 ms 14380 KB Output is correct
9 Correct 8 ms 14412 KB Output is correct
10 Correct 6 ms 14416 KB Output is correct
11 Correct 6 ms 14416 KB Output is correct
12 Correct 6 ms 14416 KB Output is correct
13 Correct 486 ms 16844 KB Output is correct
14 Correct 662 ms 19260 KB Output is correct
15 Correct 688 ms 19256 KB Output is correct
16 Correct 677 ms 19256 KB Output is correct
17 Correct 584 ms 16848 KB Output is correct
18 Correct 713 ms 19256 KB Output is correct
19 Correct 738 ms 19256 KB Output is correct
20 Correct 647 ms 19264 KB Output is correct
21 Correct 367 ms 14544 KB Output is correct
22 Correct 649 ms 14632 KB Output is correct
23 Correct 624 ms 14660 KB Output is correct
24 Correct 619 ms 14672 KB Output is correct
25 Correct 736 ms 21676 KB Output is correct
26 Correct 706 ms 21804 KB Output is correct
27 Correct 799 ms 21812 KB Output is correct
28 Correct 556 ms 21716 KB Output is correct
29 Correct 729 ms 24916 KB Output is correct
30 Correct 730 ms 24872 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14288 KB Output is correct
2 Correct 8 ms 14288 KB Output is correct
3 Correct 6 ms 14416 KB Output is correct
4 Correct 6 ms 14416 KB Output is correct
5 Correct 6 ms 14416 KB Output is correct
6 Correct 7 ms 14408 KB Output is correct
7 Correct 6 ms 14416 KB Output is correct
8 Correct 7 ms 14368 KB Output is correct
9 Correct 7 ms 14288 KB Output is correct
10 Correct 7 ms 14416 KB Output is correct
11 Correct 8 ms 14372 KB Output is correct
12 Correct 6 ms 14416 KB Output is correct
13 Correct 7 ms 14324 KB Output is correct
14 Correct 8 ms 14416 KB Output is correct
15 Correct 8 ms 14416 KB Output is correct
16 Correct 7 ms 14380 KB Output is correct
17 Correct 8 ms 14412 KB Output is correct
18 Correct 6 ms 14416 KB Output is correct
19 Correct 6 ms 14416 KB Output is correct
20 Correct 6 ms 14416 KB Output is correct
21 Incorrect 6 ms 14416 KB 1st lines differ - on the 1st token, expected: '759476520', found: '833967706'
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14288 KB Output is correct
2 Correct 8 ms 14288 KB Output is correct
3 Correct 6 ms 14416 KB Output is correct
4 Correct 6 ms 14416 KB Output is correct
5 Correct 6 ms 14416 KB Output is correct
6 Correct 7 ms 14408 KB Output is correct
7 Correct 6 ms 14416 KB Output is correct
8 Correct 7 ms 14368 KB Output is correct
9 Correct 7 ms 14288 KB Output is correct
10 Correct 7 ms 14416 KB Output is correct
11 Correct 8 ms 14372 KB Output is correct
12 Correct 6 ms 14416 KB Output is correct
13 Correct 7 ms 14324 KB Output is correct
14 Correct 8 ms 14416 KB Output is correct
15 Correct 8 ms 14416 KB Output is correct
16 Correct 7 ms 14380 KB Output is correct
17 Correct 8 ms 14412 KB Output is correct
18 Correct 6 ms 14416 KB Output is correct
19 Correct 6 ms 14416 KB Output is correct
20 Correct 6 ms 14416 KB Output is correct
21 Incorrect 6 ms 14416 KB 1st lines differ - on the 1st token, expected: '759476520', found: '833967706'
22 Halted 0 ms 0 KB -