oj.uz

Submission #914471

# Submission time Handle Problem Language Result Execution time Memory
914471 2024-01-22T08:29:23 Z ALTAKEXE Digital Circuit (IOI22_circuit) C++17
52 / 100
 708 ms 50768 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[10000001], sz[10000001], v[1000001], d1[2000001], d2[2000001];
bool lz[2000001];
vector<ll> d[1000001];
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 9 ms 31320 KB Output is correct
2 Correct 10 ms 31572 KB Output is correct
3 Correct 10 ms 33368 KB Output is correct
4 Correct 9 ms 31320 KB Output is correct
5 Correct 11 ms 31320 KB Output is correct
6 Correct 9 ms 31320 KB Output is correct
7 Correct 10 ms 31320 KB Output is correct
8 Correct 10 ms 33368 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31320 KB Output is correct
2 Correct 10 ms 31572 KB Output is correct
3 Correct 10 ms 33368 KB Output is correct
4 Correct 9 ms 31320 KB Output is correct
5 Correct 11 ms 31320 KB Output is correct
6 Correct 9 ms 31320 KB Output is correct
7 Correct 10 ms 31320 KB Output is correct
8 Correct 10 ms 33368 KB Output is correct
9 Correct 10 ms 31320 KB Output is correct
10 Correct 10 ms 33368 KB Output is correct
11 Correct 9 ms 31320 KB Output is correct
12 Correct 9 ms 33368 KB Output is correct
13 Correct 9 ms 31320 KB Output is correct
14 Correct 9 ms 31572 KB Output is correct
15 Correct 9 ms 33368 KB Output is correct
16 Correct 11 ms 33368 KB Output is correct
17 Correct 10 ms 33368 KB Output is correct
18 Correct 9 ms 33368 KB Output is correct
19 Correct 9 ms 31320 KB Output is correct
20 Correct 10 ms 31320 KB Output is correct
21 Incorrect 9 ms 31320 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 387 ms 36132 KB Output is correct
2 Correct 586 ms 42064 KB Output is correct
3 Correct 612 ms 40872 KB Output is correct
4 Correct 596 ms 40596 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 36132 KB Output is correct
2 Correct 586 ms 42064 KB Output is correct
3 Correct 612 ms 40872 KB Output is correct
4 Correct 596 ms 40596 KB Output is correct
5 Correct 492 ms 37664 KB Output is correct
6 Correct 707 ms 42148 KB Output is correct
7 Correct 645 ms 41956 KB Output is correct
8 Correct 563 ms 41048 KB Output is correct
9 Correct 265 ms 31576 KB Output is correct
10 Correct 556 ms 31576 KB Output is correct
11 Correct 581 ms 33624 KB Output is correct
12 Correct 578 ms 31576 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31320 KB Output is correct
2 Correct 10 ms 33368 KB Output is correct
3 Correct 9 ms 31320 KB Output is correct
4 Correct 9 ms 33368 KB Output is correct
5 Correct 9 ms 31320 KB Output is correct
6 Correct 9 ms 31572 KB Output is correct
7 Correct 9 ms 33368 KB Output is correct
8 Correct 11 ms 33368 KB Output is correct
9 Correct 10 ms 33368 KB Output is correct
10 Correct 9 ms 33368 KB Output is correct
11 Correct 9 ms 31320 KB Output is correct
12 Correct 10 ms 31320 KB Output is correct
13 Correct 387 ms 36132 KB Output is correct
14 Correct 586 ms 42064 KB Output is correct
15 Correct 612 ms 40872 KB Output is correct
16 Correct 596 ms 40596 KB Output is correct
17 Correct 492 ms 37664 KB Output is correct
18 Correct 707 ms 42148 KB Output is correct
19 Correct 645 ms 41956 KB Output is correct
20 Correct 563 ms 41048 KB Output is correct
21 Correct 265 ms 31576 KB Output is correct
22 Correct 556 ms 31576 KB Output is correct
23 Correct 581 ms 33624 KB Output is correct
24 Correct 578 ms 31576 KB Output is correct
25 Correct 639 ms 48356 KB Output is correct
26 Correct 708 ms 47572 KB Output is correct
27 Correct 655 ms 48180 KB Output is correct
28 Correct 501 ms 46852 KB Output is correct
29 Correct 693 ms 50736 KB Output is correct
30 Correct 593 ms 50768 KB Output is correct

Subtask #7
0 / 28.0

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