oj.uz

Submission #914473

# Submission time Handle Problem Language Result Execution time Memory
914473 2024-01-22T08:30:35 Z ALTAKEXE Digital Circuit (IOI22_circuit) C++17
52 / 100
 687 ms 47648 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[20000001];
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 8 ms 31320 KB Output is correct
3 Correct 11 ms 33368 KB Output is correct
4 Correct 9 ms 31576 KB Output is correct
5 Correct 9 ms 31320 KB Output is correct
6 Correct 9 ms 31576 KB Output is correct
7 Correct 9 ms 31320 KB Output is correct
8 Correct 11 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 10 ms 31320 KB Output is correct
4 Correct 10 ms 33488 KB Output is correct
5 Correct 10 ms 31344 KB Output is correct
6 Correct 9 ms 31320 KB Output is correct
7 Correct 10 ms 33368 KB Output is correct
8 Correct 11 ms 33368 KB Output is correct
9 Correct 9 ms 33368 KB Output is correct
10 Correct 10 ms 33368 KB Output is correct
11 Correct 9 ms 31320 KB Output is correct
12 Correct 10 ms 31400 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 8 ms 31320 KB Output is correct
3 Correct 11 ms 33368 KB Output is correct
4 Correct 9 ms 31576 KB Output is correct
5 Correct 9 ms 31320 KB Output is correct
6 Correct 9 ms 31576 KB Output is correct
7 Correct 9 ms 31320 KB Output is correct
8 Correct 11 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 10 ms 31320 KB Output is correct
12 Correct 10 ms 33488 KB Output is correct
13 Correct 10 ms 31344 KB Output is correct
14 Correct 9 ms 31320 KB Output is correct
15 Correct 10 ms 33368 KB Output is correct
16 Correct 11 ms 33368 KB Output is correct
17 Correct 9 ms 33368 KB Output is correct
18 Correct 10 ms 33368 KB Output is correct
19 Correct 9 ms 31320 KB Output is correct
20 Correct 10 ms 31400 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 362 ms 37720 KB Output is correct
2 Correct 562 ms 43160 KB Output is correct
3 Correct 546 ms 41304 KB Output is correct
4 Correct 582 ms 39924 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 37720 KB Output is correct
2 Correct 562 ms 43160 KB Output is correct
3 Correct 546 ms 41304 KB Output is correct
4 Correct 582 ms 39924 KB Output is correct
5 Correct 481 ms 39256 KB Output is correct
6 Correct 557 ms 43168 KB Output is correct
7 Correct 614 ms 43152 KB Output is correct
8 Correct 593 ms 40104 KB Output is correct
9 Correct 263 ms 31576 KB Output is correct
10 Correct 569 ms 33624 KB Output is correct
11 Correct 580 ms 35672 KB Output is correct
12 Correct 539 ms 33624 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 10 ms 31320 KB Output is correct
4 Correct 10 ms 33488 KB Output is correct
5 Correct 10 ms 31344 KB Output is correct
6 Correct 9 ms 31320 KB Output is correct
7 Correct 10 ms 33368 KB Output is correct
8 Correct 11 ms 33368 KB Output is correct
9 Correct 9 ms 33368 KB Output is correct
10 Correct 10 ms 33368 KB Output is correct
11 Correct 9 ms 31320 KB Output is correct
12 Correct 10 ms 31400 KB Output is correct
13 Correct 362 ms 37720 KB Output is correct
14 Correct 562 ms 43160 KB Output is correct
15 Correct 546 ms 41304 KB Output is correct
16 Correct 582 ms 39924 KB Output is correct
17 Correct 481 ms 39256 KB Output is correct
18 Correct 557 ms 43168 KB Output is correct
19 Correct 614 ms 43152 KB Output is correct
20 Correct 593 ms 40104 KB Output is correct
21 Correct 263 ms 31576 KB Output is correct
22 Correct 569 ms 33624 KB Output is correct
23 Correct 580 ms 35672 KB Output is correct
24 Correct 539 ms 33624 KB Output is correct
25 Correct 662 ms 44004 KB Output is correct
26 Correct 687 ms 44880 KB Output is correct
27 Correct 631 ms 45092 KB Output is correct
28 Correct 465 ms 45140 KB Output is correct
29 Correct 669 ms 46644 KB Output is correct
30 Correct 604 ms 47648 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 8 ms 31320 KB Output is correct
3 Correct 11 ms 33368 KB Output is correct
4 Correct 9 ms 31576 KB Output is correct
5 Correct 9 ms 31320 KB Output is correct
6 Correct 9 ms 31576 KB Output is correct
7 Correct 9 ms 31320 KB Output is correct
8 Correct 11 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 10 ms 31320 KB Output is correct
12 Correct 10 ms 33488 KB Output is correct
13 Correct 10 ms 31344 KB Output is correct
14 Correct 9 ms 31320 KB Output is correct
15 Correct 10 ms 33368 KB Output is correct
16 Correct 11 ms 33368 KB Output is correct
17 Correct 9 ms 33368 KB Output is correct
18 Correct 10 ms 33368 KB Output is correct
19 Correct 9 ms 31320 KB Output is correct
20 Correct 10 ms 31400 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 8 ms 31320 KB Output is correct
3 Correct 11 ms 33368 KB Output is correct
4 Correct 9 ms 31576 KB Output is correct
5 Correct 9 ms 31320 KB Output is correct
6 Correct 9 ms 31576 KB Output is correct
7 Correct 9 ms 31320 KB Output is correct
8 Correct 11 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 10 ms 31320 KB Output is correct
12 Correct 10 ms 33488 KB Output is correct
13 Correct 10 ms 31344 KB Output is correct
14 Correct 9 ms 31320 KB Output is correct
15 Correct 10 ms 33368 KB Output is correct
16 Correct 11 ms 33368 KB Output is correct
17 Correct 9 ms 33368 KB Output is correct
18 Correct 10 ms 33368 KB Output is correct
19 Correct 9 ms 31320 KB Output is correct
20 Correct 10 ms 31400 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 -