oj.uz

Submission #826747

# Submission time Handle Problem Language Result Execution time Memory
826747 2023-08-16T01:37:22 Z LittleCube Digital Circuit (IOI22_circuit) C++17
100 / 100
 870 ms 33200 KB 
#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll mod = 1'000'002'022;
namespace
{
  int N, M;
  ll ways[200005], s[100005];
  ll seg[400005], lazy[400005];
  vector<int> child[100005];

  void init_seg(int i = 1, int L = 0, int R = M - 1)
  {
    if (L == R)
    {
      seg[i] = s[L];
      return;
    }
    int mid = (L + R) / 2;
    init_seg(i << 1, L, mid);
    init_seg(i << 1 | 1, mid + 1, R);
    seg[i] = (seg[i << 1] + seg[i << 1 | 1]) % mod;
  }
  ll ans = 0;
  ll modify(int mL, int mR, int i = 1, int L = 0, int R = M - 1)
  {
    if (mL <= L && R <= mR)
    {
      lazy[i] ^= 1, seg[i] = -seg[i];
      return -seg[i];
    }
    else if (R < mL || mR < L)
      return 0;
    else
    {
      int mid = (L + R) / 2;
      if (lazy[i])
      {
        lazy[i] = 0;
        lazy[i << 1] ^= 1;
        lazy[i << 1 | 1] ^= 1;
        seg[i << 1] = -seg[i << 1];
        seg[i << 1 | 1] = -seg[i << 1 | 1];
      }
      ll res = (modify(mL, mR, i << 1, L, mid) +
                modify(mL, mR, i << 1 | 1, mid + 1, R)) %
               mod;
      seg[i] = (seg[i << 1] + seg[i << 1 | 1]) % mod;
      return res;
    }
  }

  void dfs(int u, ll up)
  {
    if (u >= N)
      s[u - N] = up;
    else
    {
      int k = child[u].size();
      vector<ll> pre(k + 1, 1), suf(k + 1, 1);
      for (int i = 0; i < k; i++)
        pre[i + 1] = pre[i] * ways[child[u][i]] % mod;
      for (int i = k - 1; i >= 0; i--)
        suf[i] = suf[i + 1] * ways[child[u][i]] % mod;
      for (int i = 0; i < k; i++)
        dfs(child[u][i], up * pre[i] % mod * suf[i + 1] % mod);
    }
  }
}

void init(int N, int M, vector<int> P, vector<int> A)
{
  ::M = M;
  ::N = N;
  for (int i = N + M - 1; i >= N; i--)
  {
    child[P[i]].emplace_back(i);
    ways[i] = 1;
  }
  for (int i = N - 1; i >= 0; i--)
  {
    if (i)
      child[P[i]].emplace_back(i);
    ways[i] = child[i].size();
    for (int j : child[i])
      ways[i] = ways[i] * ways[j] % mod;
  }
  dfs(0, 1);
  init_seg();
  for (int i = 0; i < M; i++)
    if (A[i])
      ans = (ans + modify(i, i)) % mod;
}

int count_ways(int L, int R)
{
  L -= N, R -= N;
  ans = (ans + modify(L, R)) % mod;
  return (ans + mod) % mod;
}

Subtask #1
2.0 / 2.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 ms 2640 KB Output is correct
4 Correct 1 ms 2640 KB Output is correct
5 Correct 2 ms 2640 KB Output is correct
6 Correct 2 ms 2768 KB Output is correct
7 Correct 2 ms 2704 KB Output is correct
8 Correct 2 ms 2768 KB Output is correct
9 Correct 2 ms 2768 KB Output is correct
10 Correct 2 ms 2896 KB Output is correct
11 Correct 2 ms 2896 KB Output is correct
12 Correct 2 ms 2768 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 ms 2640 KB Output is correct
4 Correct 1 ms 2756 KB Output is correct
5 Correct 2 ms 2640 KB Output is correct
6 Correct 2 ms 2640 KB Output is correct
7 Correct 2 ms 2640 KB Output is correct
8 Correct 2 ms 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 1 ms 2640 KB Output is correct
11 Correct 1 ms 2640 KB Output is correct
12 Correct 1 ms 2640 KB Output is correct
13 Correct 2 ms 2640 KB Output is correct
14 Correct 2 ms 2768 KB Output is correct
15 Correct 2 ms 2704 KB Output is correct
16 Correct 2 ms 2768 KB Output is correct
17 Correct 2 ms 2768 KB Output is correct
18 Correct 2 ms 2896 KB Output is correct
19 Correct 2 ms 2896 KB Output is correct
20 Correct 2 ms 2768 KB Output is correct
21 Correct 2 ms 2768 KB Output is correct
22 Correct 1 ms 2640 KB Output is correct
23 Correct 2 ms 2640 KB Output is correct
24 Correct 2 ms 2768 KB Output is correct
25 Correct 3 ms 2764 KB Output is correct
26 Correct 2 ms 2768 KB Output is correct
27 Correct 2 ms 2768 KB Output is correct
28 Correct 2 ms 2768 KB Output is correct
29 Correct 1 ms 2640 KB Output is correct
30 Correct 2 ms 2640 KB Output is correct
31 Correct 2 ms 2896 KB Output is correct
32 Correct 2 ms 2768 KB Output is correct
33 Correct 2 ms 2640 KB Output is correct
34 Correct 2 ms 2640 KB Output is correct
35 Correct 2 ms 2640 KB Output is correct
36 Correct 2 ms 2896 KB Output is correct
37 Correct 2 ms 2896 KB Output is correct
38 Correct 2 ms 2896 KB Output is correct
39 Correct 1 ms 2640 KB Output is correct
40 Correct 2 ms 2640 KB Output is correct
41 Correct 2 ms 2640 KB Output is correct
42 Correct 1 ms 2640 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 5924 KB Output is correct
2 Correct 784 ms 9284 KB Output is correct
3 Correct 799 ms 9236 KB Output is correct
4 Correct 675 ms 8780 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 5924 KB Output is correct
2 Correct 784 ms 9284 KB Output is correct
3 Correct 799 ms 9236 KB Output is correct
4 Correct 675 ms 8780 KB Output is correct
5 Correct 547 ms 5980 KB Output is correct
6 Correct 731 ms 9288 KB Output is correct
7 Correct 755 ms 9248 KB Output is correct
8 Correct 599 ms 9244 KB Output is correct
9 Correct 318 ms 2896 KB Output is correct
10 Correct 778 ms 3024 KB Output is correct
11 Correct 689 ms 3024 KB Output is correct
12 Correct 571 ms 3024 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 ms 2640 KB Output is correct
4 Correct 1 ms 2640 KB Output is correct
5 Correct 2 ms 2640 KB Output is correct
6 Correct 2 ms 2768 KB Output is correct
7 Correct 2 ms 2704 KB Output is correct
8 Correct 2 ms 2768 KB Output is correct
9 Correct 2 ms 2768 KB Output is correct
10 Correct 2 ms 2896 KB Output is correct
11 Correct 2 ms 2896 KB Output is correct
12 Correct 2 ms 2768 KB Output is correct
13 Correct 416 ms 5924 KB Output is correct
14 Correct 784 ms 9284 KB Output is correct
15 Correct 799 ms 9236 KB Output is correct
16 Correct 675 ms 8780 KB Output is correct
17 Correct 547 ms 5980 KB Output is correct
18 Correct 731 ms 9288 KB Output is correct
19 Correct 755 ms 9248 KB Output is correct
20 Correct 599 ms 9244 KB Output is correct
21 Correct 318 ms 2896 KB Output is correct
22 Correct 778 ms 3024 KB Output is correct
23 Correct 689 ms 3024 KB Output is correct
24 Correct 571 ms 3024 KB Output is correct
25 Correct 748 ms 13896 KB Output is correct
26 Correct 760 ms 14060 KB Output is correct
27 Correct 780 ms 14040 KB Output is correct
28 Correct 580 ms 14036 KB Output is correct
29 Correct 840 ms 32756 KB Output is correct
30 Correct 870 ms 32760 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 ms 2640 KB Output is correct
4 Correct 1 ms 2756 KB Output is correct
5 Correct 2 ms 2640 KB Output is correct
6 Correct 2 ms 2640 KB Output is correct
7 Correct 2 ms 2640 KB Output is correct
8 Correct 2 ms 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 1 ms 2640 KB Output is correct
11 Correct 1 ms 2640 KB Output is correct
12 Correct 1 ms 2640 KB Output is correct
13 Correct 2 ms 2640 KB Output is correct
14 Correct 2 ms 2768 KB Output is correct
15 Correct 2 ms 2704 KB Output is correct
16 Correct 2 ms 2768 KB Output is correct
17 Correct 2 ms 2768 KB Output is correct
18 Correct 2 ms 2896 KB Output is correct
19 Correct 2 ms 2896 KB Output is correct
20 Correct 2 ms 2768 KB Output is correct
21 Correct 2 ms 2768 KB Output is correct
22 Correct 1 ms 2640 KB Output is correct
23 Correct 2 ms 2640 KB Output is correct
24 Correct 2 ms 2768 KB Output is correct
25 Correct 3 ms 2764 KB Output is correct
26 Correct 2 ms 2768 KB Output is correct
27 Correct 2 ms 2768 KB Output is correct
28 Correct 2 ms 2768 KB Output is correct
29 Correct 1 ms 2640 KB Output is correct
30 Correct 2 ms 2640 KB Output is correct
31 Correct 2 ms 2896 KB Output is correct
32 Correct 2 ms 2768 KB Output is correct
33 Correct 2 ms 2640 KB Output is correct
34 Correct 2 ms 2640 KB Output is correct
35 Correct 2 ms 2640 KB Output is correct
36 Correct 2 ms 2896 KB Output is correct
37 Correct 2 ms 2896 KB Output is correct
38 Correct 2 ms 2896 KB Output is correct
39 Correct 1 ms 2640 KB Output is correct
40 Correct 2 ms 2640 KB Output is correct
41 Correct 2 ms 2640 KB Output is correct
42 Correct 1 ms 2640 KB Output is correct
43 Correct 560 ms 3024 KB Output is correct
44 Correct 644 ms 3024 KB Output is correct
45 Correct 591 ms 3044 KB Output is correct
46 Correct 591 ms 3296 KB Output is correct
47 Correct 781 ms 3280 KB Output is correct
48 Correct 701 ms 3288 KB Output is correct
49 Correct 540 ms 3280 KB Output is correct
50 Correct 756 ms 3280 KB Output is correct
51 Correct 647 ms 3280 KB Output is correct
52 Correct 646 ms 3212 KB Output is correct
53 Correct 676 ms 3812 KB Output is correct
54 Correct 664 ms 3280 KB Output is correct
55 Correct 703 ms 3164 KB Output is correct
56 Correct 653 ms 3172 KB Output is correct
57 Correct 649 ms 3032 KB Output is correct
58 Correct 707 ms 4176 KB Output is correct
59 Correct 641 ms 4324 KB Output is correct
60 Correct 496 ms 4320 KB Output is correct
61 Correct 604 ms 3280 KB Output is correct
62 Correct 618 ms 2896 KB Output is correct
63 Correct 577 ms 2912 KB Output is correct
64 Correct 691 ms 3164 KB Output is correct
65 Correct 296 ms 2896 KB Output is correct
66 Correct 692 ms 3024 KB Output is correct
67 Correct 740 ms 3024 KB Output is correct
68 Correct 747 ms 3040 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 ms 2640 KB Output is correct
4 Correct 1 ms 2756 KB Output is correct
5 Correct 2 ms 2640 KB Output is correct
6 Correct 2 ms 2640 KB Output is correct
7 Correct 2 ms 2640 KB Output is correct
8 Correct 2 ms 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 1 ms 2640 KB Output is correct
11 Correct 1 ms 2640 KB Output is correct
12 Correct 1 ms 2640 KB Output is correct
13 Correct 2 ms 2640 KB Output is correct
14 Correct 2 ms 2768 KB Output is correct
15 Correct 2 ms 2704 KB Output is correct
16 Correct 2 ms 2768 KB Output is correct
17 Correct 2 ms 2768 KB Output is correct
18 Correct 2 ms 2896 KB Output is correct
19 Correct 2 ms 2896 KB Output is correct
20 Correct 2 ms 2768 KB Output is correct
21 Correct 2 ms 2768 KB Output is correct
22 Correct 1 ms 2640 KB Output is correct
23 Correct 2 ms 2640 KB Output is correct
24 Correct 2 ms 2768 KB Output is correct
25 Correct 3 ms 2764 KB Output is correct
26 Correct 2 ms 2768 KB Output is correct
27 Correct 2 ms 2768 KB Output is correct
28 Correct 2 ms 2768 KB Output is correct
29 Correct 1 ms 2640 KB Output is correct
30 Correct 2 ms 2640 KB Output is correct
31 Correct 2 ms 2896 KB Output is correct
32 Correct 2 ms 2768 KB Output is correct
33 Correct 2 ms 2640 KB Output is correct
34 Correct 2 ms 2640 KB Output is correct
35 Correct 2 ms 2640 KB Output is correct
36 Correct 2 ms 2896 KB Output is correct
37 Correct 2 ms 2896 KB Output is correct
38 Correct 2 ms 2896 KB Output is correct
39 Correct 1 ms 2640 KB Output is correct
40 Correct 2 ms 2640 KB Output is correct
41 Correct 2 ms 2640 KB Output is correct
42 Correct 1 ms 2640 KB Output is correct
43 Correct 416 ms 5924 KB Output is correct
44 Correct 784 ms 9284 KB Output is correct
45 Correct 799 ms 9236 KB Output is correct
46 Correct 675 ms 8780 KB Output is correct
47 Correct 547 ms 5980 KB Output is correct
48 Correct 731 ms 9288 KB Output is correct
49 Correct 755 ms 9248 KB Output is correct
50 Correct 599 ms 9244 KB Output is correct
51 Correct 318 ms 2896 KB Output is correct
52 Correct 778 ms 3024 KB Output is correct
53 Correct 689 ms 3024 KB Output is correct
54 Correct 571 ms 3024 KB Output is correct
55 Correct 748 ms 13896 KB Output is correct
56 Correct 760 ms 14060 KB Output is correct
57 Correct 780 ms 14040 KB Output is correct
58 Correct 580 ms 14036 KB Output is correct
59 Correct 840 ms 32756 KB Output is correct
60 Correct 870 ms 32760 KB Output is correct
61 Correct 560 ms 3024 KB Output is correct
62 Correct 644 ms 3024 KB Output is correct
63 Correct 591 ms 3044 KB Output is correct
64 Correct 591 ms 3296 KB Output is correct
65 Correct 781 ms 3280 KB Output is correct
66 Correct 701 ms 3288 KB Output is correct
67 Correct 540 ms 3280 KB Output is correct
68 Correct 756 ms 3280 KB Output is correct
69 Correct 647 ms 3280 KB Output is correct
70 Correct 646 ms 3212 KB Output is correct
71 Correct 676 ms 3812 KB Output is correct
72 Correct 664 ms 3280 KB Output is correct
73 Correct 703 ms 3164 KB Output is correct
74 Correct 653 ms 3172 KB Output is correct
75 Correct 649 ms 3032 KB Output is correct
76 Correct 707 ms 4176 KB Output is correct
77 Correct 641 ms 4324 KB Output is correct
78 Correct 496 ms 4320 KB Output is correct
79 Correct 604 ms 3280 KB Output is correct
80 Correct 618 ms 2896 KB Output is correct
81 Correct 577 ms 2912 KB Output is correct
82 Correct 691 ms 3164 KB Output is correct
83 Correct 296 ms 2896 KB Output is correct
84 Correct 692 ms 3024 KB Output is correct
85 Correct 740 ms 3024 KB Output is correct
86 Correct 747 ms 3040 KB Output is correct
87 Correct 1 ms 2640 KB Output is correct
88 Correct 441 ms 13188 KB Output is correct
89 Correct 736 ms 9688 KB Output is correct
90 Correct 711 ms 9432 KB Output is correct
91 Correct 829 ms 14168 KB Output is correct
92 Correct 779 ms 14156 KB Output is correct
93 Correct 804 ms 13552 KB Output is correct
94 Correct 727 ms 14196 KB Output is correct
95 Correct 702 ms 14088 KB Output is correct
96 Correct 627 ms 9916 KB Output is correct
97 Correct 759 ms 9904 KB Output is correct
98 Correct 753 ms 26072 KB Output is correct
99 Correct 771 ms 14064 KB Output is correct
100 Correct 646 ms 11692 KB Output is correct
101 Correct 768 ms 11080 KB Output is correct
102 Correct 815 ms 9928 KB Output is correct
103 Correct 845 ms 32852 KB Output is correct
104 Correct 777 ms 33156 KB Output is correct
105 Correct 719 ms 33200 KB Output is correct
106 Correct 821 ms 13556 KB Output is correct
107 Correct 863 ms 10256 KB Output is correct
108 Correct 826 ms 10248 KB Output is correct
109 Correct 752 ms 10072 KB Output is correct