oj.uz

Submission #910930

# Submission time Handle Problem Language Result Execution time Memory
910930 2024-01-18T09:46:07 Z ALTAKEXE Digital Circuit (IOI22_circuit) C++17
25 / 100
 622 ms 20192 KB 
#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
const ll MOD = 1000002022;
int n, m;
ll p[1000001], sz[1000001], v[100001], d1[200001], d2[200001];
bool lz[2000001];
vector<ll> d[100001];
void dfs(int u)
{
  for (auto v : d[u])
  {
    sz[v] = sz[u] + 1;
    dfs(v);
  }
}
void build(int l, int r, int i, vector<int> &t)
{
  if (l == r)
  {
    if (t[l])
    {
      d1[i] = v[l];
    }
    else
    {
      d2[i] = v[l];
    }
    return;
  }
  int md = (l + r) / 2;
  build(l, md, 2 * i, t);
  build(md + 1, r, 2 * i + 1, t);
  d1[i] = (d1[2 * i] + d1[2 * i + 1]) % MOD;
  d2[i] = (d2[2 * i] + d2[2 * i + 1]) % MOD;
}
void lazy(int l, int r, int i)
{
  if (!lz[i])
    return;
  lz[i] = 0;
  swap(d1[i], d2[i]);
  if (l == r)
    return;
  lz[2 * i] = !lz[2 * i];
  lz[2 * i + 1] = !lz[2 * i + 1];
}
void update(int l, int r, int i, int ql, int qr)
{
  lazy(l, r, i);
  if (r < ql || qr < l)
    return;
  if (ql <= l && r <= qr)
  {
    lz[i] = 1;
    lazy(l, r, i);
    return;
  }
  int md = (l + r) / 2;
  update(l, md, 2 * i, ql, qr);
  update(md + 1, r, 2 * i + 1, ql, qr);
  d1[i] = (d1[2 * i] + d1[2 * i + 1]) % MOD;
  d2[i] = (d2[2 * i] + d2[2 * i + 1]) % MOD;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
  p[0] = 1;
  n = N;
  m = M;
  for (int i = 1; i < N + M; i++)
    p[i] = (p[i - 1] * 2) % MOD;
  for (int i = 1; i < N + M; i++)
    d[P[i]].push_back(i);
  dfs(0);
  for (int i = N; i < N + M; i++)
    v[i - N] = p[N - sz[i]];
  build(0, M - 1, 1, A);
}

int count_ways(int L, int R)
{
  update(0, m - 1, 1, L - n, R - n);
  return d1[1];
}

Subtask #1
2.0 / 2.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8788 KB Output is correct
7 Correct 3 ms 8792 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 3 ms 8792 KB Output is correct
11 Correct 2 ms 9044 KB Output is correct
12 Correct 3 ms 8792 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 3 ms 8792 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Correct 2 ms 8792 KB Output is correct
8 Correct 2 ms 8824 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 2 ms 8792 KB Output is correct
12 Correct 2 ms 8792 KB Output is correct
13 Correct 2 ms 8792 KB Output is correct
14 Correct 2 ms 8788 KB Output is correct
15 Correct 3 ms 8792 KB Output is correct
16 Correct 2 ms 8792 KB Output is correct
17 Correct 2 ms 8792 KB Output is correct
18 Correct 3 ms 8792 KB Output is correct
19 Correct 2 ms 9044 KB Output is correct
20 Correct 3 ms 8792 KB Output is correct
21 Incorrect 2 ms 8792 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 407 ms 13144 KB Output is correct
2 Correct 589 ms 17788 KB Output is correct
3 Correct 612 ms 17788 KB Output is correct
4 Correct 540 ms 17280 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 13144 KB Output is correct
2 Correct 589 ms 17788 KB Output is correct
3 Correct 612 ms 17788 KB Output is correct
4 Correct 540 ms 17280 KB Output is correct
5 Correct 483 ms 13056 KB Output is correct
6 Correct 605 ms 17784 KB Output is correct
7 Correct 622 ms 17784 KB Output is correct
8 Correct 534 ms 17784 KB Output is correct
9 Correct 238 ms 8792 KB Output is correct
10 Correct 568 ms 9048 KB Output is correct
11 Correct 506 ms 9048 KB Output is correct
12 Correct 513 ms 9048 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8788 KB Output is correct
7 Correct 3 ms 8792 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 3 ms 8792 KB Output is correct
11 Correct 2 ms 9044 KB Output is correct
12 Correct 3 ms 8792 KB Output is correct
13 Correct 407 ms 13144 KB Output is correct
14 Correct 589 ms 17788 KB Output is correct
15 Correct 612 ms 17788 KB Output is correct
16 Correct 540 ms 17280 KB Output is correct
17 Correct 483 ms 13056 KB Output is correct
18 Correct 605 ms 17784 KB Output is correct
19 Correct 622 ms 17784 KB Output is correct
20 Correct 534 ms 17784 KB Output is correct
21 Correct 238 ms 8792 KB Output is correct
22 Correct 568 ms 9048 KB Output is correct
23 Correct 506 ms 9048 KB Output is correct
24 Correct 513 ms 9048 KB Output is correct
25 Incorrect 621 ms 20192 KB 1st lines differ - on the 1st token, expected: '732332002', found: '669877922'
26 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 3 ms 8792 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Correct 2 ms 8792 KB Output is correct
8 Correct 2 ms 8824 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 2 ms 8792 KB Output is correct
12 Correct 2 ms 8792 KB Output is correct
13 Correct 2 ms 8792 KB Output is correct
14 Correct 2 ms 8788 KB Output is correct
15 Correct 3 ms 8792 KB Output is correct
16 Correct 2 ms 8792 KB Output is correct
17 Correct 2 ms 8792 KB Output is correct
18 Correct 3 ms 8792 KB Output is correct
19 Correct 2 ms 9044 KB Output is correct
20 Correct 3 ms 8792 KB Output is correct
21 Incorrect 2 ms 8792 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 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 3 ms 8792 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Correct 2 ms 8792 KB Output is correct
8 Correct 2 ms 8824 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 2 ms 8792 KB Output is correct
12 Correct 2 ms 8792 KB Output is correct
13 Correct 2 ms 8792 KB Output is correct
14 Correct 2 ms 8788 KB Output is correct
15 Correct 3 ms 8792 KB Output is correct
16 Correct 2 ms 8792 KB Output is correct
17 Correct 2 ms 8792 KB Output is correct
18 Correct 3 ms 8792 KB Output is correct
19 Correct 2 ms 9044 KB Output is correct
20 Correct 3 ms 8792 KB Output is correct
21 Incorrect 2 ms 8792 KB 1st lines differ - on the 1st token, expected: '759476520', found: '833967706'
22 Halted 0 ms 0 KB -