oj.uz

Submission #639774

# Submission time Handle Problem Language Result Execution time Memory
639774 2022-09-11T15:09:18 Z study Digital Circuit (IOI22_circuit) C++17
100 / 100
 1116 ms 36692 KB 
#include <bits/stdc++.h>
#include "circuit.h"
using ll=long long;
using namespace std;

const ll mod = 1e9+2022, N = 1e5+1, M = 1e5+1;
pair<ll,ll> segt[4*N+5];
bool lazy[4*N+5],vu[N+M];
ll prod[2*N];
vector<int> adj[N+M],rev[N+M];
int n=0, m = 0, stop = -1;
bool ok = false;
pair<ll,ll> crt;
vector<int> pre,nouv,order;

void modify(int idx, int l, int r, int L, int R){
	if (r < L or l > R) return;
	if (l >= L and r <= R){
		if (ok){
			swap(segt[idx].first,segt[idx].second);
			lazy[idx] = !lazy[idx];
		}
		else{
			segt[idx] = crt;
		}
		return;
	}
	if (lazy[idx]){
		lazy[2*idx] = !lazy[2*idx];
		lazy[2*idx+1] = !lazy[2*idx+1];
		swap(segt[2*idx].first,segt[2*idx].second);
		swap(segt[2*idx+1].first,segt[2*idx+1].second);
		lazy[idx] = 0;
	}
	int mid = (l+r)/2;
	modify(2*idx,l,mid,L,R);
	modify(2*idx+1,mid+1,r,L,R);
	segt[idx].first = (segt[2*idx].first+segt[2*idx+1].first)%mod;
	segt[idx].second = (segt[2*idx].second+segt[2*idx+1].second)%mod;
}

void euler_tour(int node){
	if (node >= n){
		order.emplace_back(node-n);
	}
	for (int i:rev[node]){
		euler_tour(i);
	}
}

void dfs(int node){
	for (int i:adj[node]){
		if (vu[i]){
			stop = i;
			return;
		}
		nouv.emplace_back(i);
		dfs(i);
	}
}

void upd(int node, int val){
	node += N;
	prod[node] = val;
	node >>= 1;
	while (node){
		prod[node] = (prod[2*node]*prod[2*node+1])%mod;
		node >>= 1;
	}
}

ll query(int l, int r){
	l += N;
	r += N;
	ll ans = 1;
	while (l <= r){
		if (l&1){
			ans = (ans*prod[l])%mod;
			l++;
		}
		if (r%2 == 0){
			ans = (ans*prod[r])%mod;
			r--;
		}
		l >>= 1;
		r >>= 1;
	}
	return ans;
}

void init(int N, int M, vector<int> P, vector<int> A){
	m = M;
	n = N;
	vector<ll> deg(N+M);
	for (int i=1; i<N+M; ++i){
		deg[P[i]]++;
		adj[i].emplace_back(P[i]);
		rev[P[i]].emplace_back(i);
	}
	fill_n(&prod[0],2*N,1);
	for (int i=0; i<N; ++i) upd(i,deg[i]);
	euler_tour(0);
	for (int i:order){
		stop = -1;
		nouv.clear();
		dfs(i+n);
		while (!pre.empty() and pre.back() != stop){
			upd(pre.back(),deg[pre.back()]);
			vu[pre.back()] = false;
			pre.pop_back();
		}
		reverse(nouv.begin(),nouv.end());
		for (int k:nouv){
			upd(k,1);
			vu[k] = true;
			pre.emplace_back(k);
		}
		ll ans = query(0,n-1);
		if (A[i]){
			crt = {ans,0};
		}
		else{
			crt = {0,ans};
		}
		modify(1,0,M-1,i,i);
	}
	ok = true;
}

int count_ways(int L, int R){
	L -= n;
	R -= n;
	modify(1,0,m-1,L,R);
	return segt[1].first;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 5 ms 9680 KB Output is correct
3 Correct 6 ms 9808 KB Output is correct
4 Correct 5 ms 9808 KB Output is correct
5 Correct 5 ms 9848 KB Output is correct
6 Correct 6 ms 9808 KB Output is correct
7 Correct 5 ms 9808 KB Output is correct
8 Correct 6 ms 9808 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9636 KB Output is correct
2 Correct 5 ms 9680 KB Output is correct
3 Correct 5 ms 9808 KB Output is correct
4 Correct 5 ms 9808 KB Output is correct
5 Correct 5 ms 9808 KB Output is correct
6 Correct 6 ms 9852 KB Output is correct
7 Correct 6 ms 9936 KB Output is correct
8 Correct 7 ms 9936 KB Output is correct
9 Correct 6 ms 9936 KB Output is correct
10 Correct 6 ms 9936 KB Output is correct
11 Correct 6 ms 9936 KB Output is correct
12 Correct 6 ms 9808 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 5 ms 9680 KB Output is correct
3 Correct 6 ms 9808 KB Output is correct
4 Correct 5 ms 9808 KB Output is correct
5 Correct 5 ms 9848 KB Output is correct
6 Correct 6 ms 9808 KB Output is correct
7 Correct 5 ms 9808 KB Output is correct
8 Correct 6 ms 9808 KB Output is correct
9 Correct 7 ms 9636 KB Output is correct
10 Correct 5 ms 9680 KB Output is correct
11 Correct 5 ms 9808 KB Output is correct
12 Correct 5 ms 9808 KB Output is correct
13 Correct 5 ms 9808 KB Output is correct
14 Correct 6 ms 9852 KB Output is correct
15 Correct 6 ms 9936 KB Output is correct
16 Correct 7 ms 9936 KB Output is correct
17 Correct 6 ms 9936 KB Output is correct
18 Correct 6 ms 9936 KB Output is correct
19 Correct 6 ms 9936 KB Output is correct
20 Correct 6 ms 9808 KB Output is correct
21 Correct 6 ms 9808 KB Output is correct
22 Correct 5 ms 9808 KB Output is correct
23 Correct 6 ms 9808 KB Output is correct
24 Correct 6 ms 9944 KB Output is correct
25 Correct 6 ms 9936 KB Output is correct
26 Correct 6 ms 9936 KB Output is correct
27 Correct 6 ms 9936 KB Output is correct
28 Correct 6 ms 9936 KB Output is correct
29 Correct 5 ms 9808 KB Output is correct
30 Correct 6 ms 9808 KB Output is correct
31 Correct 5 ms 9808 KB Output is correct
32 Correct 6 ms 9936 KB Output is correct
33 Correct 5 ms 9808 KB Output is correct
34 Correct 5 ms 9808 KB Output is correct
35 Correct 6 ms 9856 KB Output is correct
36 Correct 6 ms 9944 KB Output is correct
37 Correct 6 ms 9916 KB Output is correct
38 Correct 6 ms 9936 KB Output is correct
39 Correct 6 ms 9808 KB Output is correct
40 Correct 5 ms 9808 KB Output is correct
41 Correct 5 ms 9808 KB Output is correct
42 Correct 6 ms 9740 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 16112 KB Output is correct
2 Correct 773 ms 22224 KB Output is correct
3 Correct 962 ms 22212 KB Output is correct
4 Correct 857 ms 22224 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 16112 KB Output is correct
2 Correct 773 ms 22224 KB Output is correct
3 Correct 962 ms 22212 KB Output is correct
4 Correct 857 ms 22224 KB Output is correct
5 Correct 750 ms 16076 KB Output is correct
6 Correct 834 ms 22200 KB Output is correct
7 Correct 975 ms 22244 KB Output is correct
8 Correct 836 ms 22220 KB Output is correct
9 Correct 441 ms 10064 KB Output is correct
10 Correct 811 ms 10448 KB Output is correct
11 Correct 836 ms 10468 KB Output is correct
12 Correct 806 ms 10448 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9636 KB Output is correct
2 Correct 5 ms 9680 KB Output is correct
3 Correct 5 ms 9808 KB Output is correct
4 Correct 5 ms 9808 KB Output is correct
5 Correct 5 ms 9808 KB Output is correct
6 Correct 6 ms 9852 KB Output is correct
7 Correct 6 ms 9936 KB Output is correct
8 Correct 7 ms 9936 KB Output is correct
9 Correct 6 ms 9936 KB Output is correct
10 Correct 6 ms 9936 KB Output is correct
11 Correct 6 ms 9936 KB Output is correct
12 Correct 6 ms 9808 KB Output is correct
13 Correct 618 ms 16112 KB Output is correct
14 Correct 773 ms 22224 KB Output is correct
15 Correct 962 ms 22212 KB Output is correct
16 Correct 857 ms 22224 KB Output is correct
17 Correct 750 ms 16076 KB Output is correct
18 Correct 834 ms 22200 KB Output is correct
19 Correct 975 ms 22244 KB Output is correct
20 Correct 836 ms 22220 KB Output is correct
21 Correct 441 ms 10064 KB Output is correct
22 Correct 811 ms 10448 KB Output is correct
23 Correct 836 ms 10468 KB Output is correct
24 Correct 806 ms 10448 KB Output is correct
25 Correct 1032 ms 29060 KB Output is correct
26 Correct 984 ms 29324 KB Output is correct
27 Correct 960 ms 29260 KB Output is correct
28 Correct 835 ms 29172 KB Output is correct
29 Correct 965 ms 36288 KB Output is correct
30 Correct 918 ms 36292 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 5 ms 9680 KB Output is correct
3 Correct 6 ms 9808 KB Output is correct
4 Correct 5 ms 9808 KB Output is correct
5 Correct 5 ms 9848 KB Output is correct
6 Correct 6 ms 9808 KB Output is correct
7 Correct 5 ms 9808 KB Output is correct
8 Correct 6 ms 9808 KB Output is correct
9 Correct 7 ms 9636 KB Output is correct
10 Correct 5 ms 9680 KB Output is correct
11 Correct 5 ms 9808 KB Output is correct
12 Correct 5 ms 9808 KB Output is correct
13 Correct 5 ms 9808 KB Output is correct
14 Correct 6 ms 9852 KB Output is correct
15 Correct 6 ms 9936 KB Output is correct
16 Correct 7 ms 9936 KB Output is correct
17 Correct 6 ms 9936 KB Output is correct
18 Correct 6 ms 9936 KB Output is correct
19 Correct 6 ms 9936 KB Output is correct
20 Correct 6 ms 9808 KB Output is correct
21 Correct 6 ms 9808 KB Output is correct
22 Correct 5 ms 9808 KB Output is correct
23 Correct 6 ms 9808 KB Output is correct
24 Correct 6 ms 9944 KB Output is correct
25 Correct 6 ms 9936 KB Output is correct
26 Correct 6 ms 9936 KB Output is correct
27 Correct 6 ms 9936 KB Output is correct
28 Correct 6 ms 9936 KB Output is correct
29 Correct 5 ms 9808 KB Output is correct
30 Correct 6 ms 9808 KB Output is correct
31 Correct 5 ms 9808 KB Output is correct
32 Correct 6 ms 9936 KB Output is correct
33 Correct 5 ms 9808 KB Output is correct
34 Correct 5 ms 9808 KB Output is correct
35 Correct 6 ms 9856 KB Output is correct
36 Correct 6 ms 9944 KB Output is correct
37 Correct 6 ms 9916 KB Output is correct
38 Correct 6 ms 9936 KB Output is correct
39 Correct 6 ms 9808 KB Output is correct
40 Correct 5 ms 9808 KB Output is correct
41 Correct 5 ms 9808 KB Output is correct
42 Correct 6 ms 9740 KB Output is correct
43 Correct 505 ms 10320 KB Output is correct
44 Correct 943 ms 10468 KB Output is correct
45 Correct 703 ms 10320 KB Output is correct
46 Correct 919 ms 10864 KB Output is correct
47 Correct 716 ms 10864 KB Output is correct
48 Correct 909 ms 10880 KB Output is correct
49 Correct 796 ms 10872 KB Output is correct
50 Correct 501 ms 10952 KB Output is correct
51 Correct 756 ms 10352 KB Output is correct
52 Correct 905 ms 10372 KB Output is correct
53 Correct 712 ms 10656 KB Output is correct
54 Correct 781 ms 10856 KB Output is correct
55 Correct 762 ms 10576 KB Output is correct
56 Correct 858 ms 10500 KB Output is correct
57 Correct 830 ms 10356 KB Output is correct
58 Correct 844 ms 11224 KB Output is correct
59 Correct 776 ms 11248 KB Output is correct
60 Correct 758 ms 11248 KB Output is correct
61 Correct 626 ms 10520 KB Output is correct
62 Correct 802 ms 10332 KB Output is correct
63 Correct 867 ms 10264 KB Output is correct
64 Correct 735 ms 10372 KB Output is correct
65 Correct 476 ms 10064 KB Output is correct
66 Correct 708 ms 10448 KB Output is correct
67 Correct 809 ms 10448 KB Output is correct
68 Correct 870 ms 10576 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 5 ms 9680 KB Output is correct
3 Correct 6 ms 9808 KB Output is correct
4 Correct 5 ms 9808 KB Output is correct
5 Correct 5 ms 9848 KB Output is correct
6 Correct 6 ms 9808 KB Output is correct
7 Correct 5 ms 9808 KB Output is correct
8 Correct 6 ms 9808 KB Output is correct
9 Correct 7 ms 9636 KB Output is correct
10 Correct 5 ms 9680 KB Output is correct
11 Correct 5 ms 9808 KB Output is correct
12 Correct 5 ms 9808 KB Output is correct
13 Correct 5 ms 9808 KB Output is correct
14 Correct 6 ms 9852 KB Output is correct
15 Correct 6 ms 9936 KB Output is correct
16 Correct 7 ms 9936 KB Output is correct
17 Correct 6 ms 9936 KB Output is correct
18 Correct 6 ms 9936 KB Output is correct
19 Correct 6 ms 9936 KB Output is correct
20 Correct 6 ms 9808 KB Output is correct
21 Correct 6 ms 9808 KB Output is correct
22 Correct 5 ms 9808 KB Output is correct
23 Correct 6 ms 9808 KB Output is correct
24 Correct 6 ms 9944 KB Output is correct
25 Correct 6 ms 9936 KB Output is correct
26 Correct 6 ms 9936 KB Output is correct
27 Correct 6 ms 9936 KB Output is correct
28 Correct 6 ms 9936 KB Output is correct
29 Correct 5 ms 9808 KB Output is correct
30 Correct 6 ms 9808 KB Output is correct
31 Correct 5 ms 9808 KB Output is correct
32 Correct 6 ms 9936 KB Output is correct
33 Correct 5 ms 9808 KB Output is correct
34 Correct 5 ms 9808 KB Output is correct
35 Correct 6 ms 9856 KB Output is correct
36 Correct 6 ms 9944 KB Output is correct
37 Correct 6 ms 9916 KB Output is correct
38 Correct 6 ms 9936 KB Output is correct
39 Correct 6 ms 9808 KB Output is correct
40 Correct 5 ms 9808 KB Output is correct
41 Correct 5 ms 9808 KB Output is correct
42 Correct 6 ms 9740 KB Output is correct
43 Correct 618 ms 16112 KB Output is correct
44 Correct 773 ms 22224 KB Output is correct
45 Correct 962 ms 22212 KB Output is correct
46 Correct 857 ms 22224 KB Output is correct
47 Correct 750 ms 16076 KB Output is correct
48 Correct 834 ms 22200 KB Output is correct
49 Correct 975 ms 22244 KB Output is correct
50 Correct 836 ms 22220 KB Output is correct
51 Correct 441 ms 10064 KB Output is correct
52 Correct 811 ms 10448 KB Output is correct
53 Correct 836 ms 10468 KB Output is correct
54 Correct 806 ms 10448 KB Output is correct
55 Correct 1032 ms 29060 KB Output is correct
56 Correct 984 ms 29324 KB Output is correct
57 Correct 960 ms 29260 KB Output is correct
58 Correct 835 ms 29172 KB Output is correct
59 Correct 965 ms 36288 KB Output is correct
60 Correct 918 ms 36292 KB Output is correct
61 Correct 505 ms 10320 KB Output is correct
62 Correct 943 ms 10468 KB Output is correct
63 Correct 703 ms 10320 KB Output is correct
64 Correct 919 ms 10864 KB Output is correct
65 Correct 716 ms 10864 KB Output is correct
66 Correct 909 ms 10880 KB Output is correct
67 Correct 796 ms 10872 KB Output is correct
68 Correct 501 ms 10952 KB Output is correct
69 Correct 756 ms 10352 KB Output is correct
70 Correct 905 ms 10372 KB Output is correct
71 Correct 712 ms 10656 KB Output is correct
72 Correct 781 ms 10856 KB Output is correct
73 Correct 762 ms 10576 KB Output is correct
74 Correct 858 ms 10500 KB Output is correct
75 Correct 830 ms 10356 KB Output is correct
76 Correct 844 ms 11224 KB Output is correct
77 Correct 776 ms 11248 KB Output is correct
78 Correct 758 ms 11248 KB Output is correct
79 Correct 626 ms 10520 KB Output is correct
80 Correct 802 ms 10332 KB Output is correct
81 Correct 867 ms 10264 KB Output is correct
82 Correct 735 ms 10372 KB Output is correct
83 Correct 476 ms 10064 KB Output is correct
84 Correct 708 ms 10448 KB Output is correct
85 Correct 809 ms 10448 KB Output is correct
86 Correct 870 ms 10576 KB Output is correct
87 Correct 5 ms 9680 KB Output is correct
88 Correct 668 ms 27756 KB Output is correct
89 Correct 871 ms 22408 KB Output is correct
90 Correct 1018 ms 21936 KB Output is correct
91 Correct 941 ms 29416 KB Output is correct
92 Correct 1087 ms 29420 KB Output is correct
93 Correct 1116 ms 29416 KB Output is correct
94 Correct 1079 ms 29408 KB Output is correct
95 Correct 1045 ms 29404 KB Output is correct
96 Correct 718 ms 20164 KB Output is correct
97 Correct 952 ms 20236 KB Output is correct
98 Correct 559 ms 26576 KB Output is correct
99 Correct 1104 ms 29252 KB Output is correct
100 Correct 1038 ms 24876 KB Output is correct
101 Correct 758 ms 22888 KB Output is correct
102 Correct 1008 ms 20328 KB Output is correct
103 Correct 865 ms 36412 KB Output is correct
104 Correct 961 ms 36688 KB Output is correct
105 Correct 817 ms 36692 KB Output is correct
106 Correct 882 ms 22864 KB Output is correct
107 Correct 1004 ms 22076 KB Output is correct
108 Correct 1010 ms 21724 KB Output is correct
109 Correct 820 ms 20308 KB Output is correct