oj.uz

Submission #643498

# Submission time Handle Problem Language Result Execution time Memory
643498 2022-09-22T08:02:52 Z Vanilla Digital Circuit (IOI22_circuit) C++17
52 / 100
 1022 ms 20552 KB 
#include <bits/stdc++.h>
#include "circuit.h"
typedef long long int64;
using namespace std;
const int64 mod = 1000002022;
const int maxn = 2e5 + 2;
vector <int> ad [maxn];
int64 depth[maxn];
int64 dp[4 * maxn]; // each node contributes 2^(N - depth)
int64 pref[4 * maxn];
int64 lazy[4 * maxn];
int64 pw [maxn];
int n,m;

void dfs (int x) {
  for (int v: ad[x]) {
    depth[v] = depth[x] + 1;
    dfs(v);
  }
}

int64 sum (int l, int r) {
  return (pref[r] - pref[l - 1] + mod) % mod;
}

void push (int x, int l, int r) {
  if (!lazy[x]) return;
  int mid = (l + r) / 2;
  dp[x * 2 + 1] = (sum(l, mid) - dp[x * 2 + 1] + mod) % mod;
  dp[x * 2 + 2] = (sum(mid + 1, r) - dp[x * 2 + 2] + mod) % mod;
  lazy[x * 2 + 1] = !lazy[x * 2 + 1];
  lazy[x * 2 + 2] = !lazy[x * 2 + 2];
  lazy[x] = 0;
}


void upd (int x, int l, int r, int il, int ir) {
  // cout << x << " " << l << " " << r << " " << il << " " << ir << "\n";
  if (il <= l && r <= ir) {
    // cout << l << " " << r << " " << sum(l, r) << "\n";
    dp[x] = (sum(l, r) - dp[x] + mod) % mod;
    lazy[x] = !lazy[x];
    return;
  }
  if (l > ir || r < il) return;
  push(x, l, r);
  int mid = (l + r) / 2;
  upd(x * 2 + 1, l, mid, il, ir);
  upd(x * 2 + 2, mid + 1, r, il, ir);
  dp[x] = (dp[x * 2 + 1] + dp[x * 2 + 2]) % mod;
}
 
void init(int N, int M, vector<int> P, vector<int> A) {
  n = N, m = M;
  pw[0] = 1;
  for (int i = 1; i < maxn; i++){
    pw[i] = pw[i-1] * 2 % mod;
  }
  for (int i = 1; i < N + M; i++){
    ad[P[i]].push_back(i);
  }
  dfs(0);
  for (int i = 0; i < M; i++){
    pref[i] = ((i ? pref[i-1]: 0) + pw[N - depth[i + N]] )% mod;
  }
  for (int i = 0; i < M; i++){
    if (A[i]) upd(0, 0, M - 1, i, i);
  }
}

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

Subtask #1
2.0 / 2.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6480 KB Output is correct
2 Correct 4 ms 6480 KB Output is correct
3 Correct 4 ms 6608 KB Output is correct
4 Correct 4 ms 6608 KB Output is correct
5 Correct 4 ms 6608 KB Output is correct
6 Correct 4 ms 6608 KB Output is correct
7 Correct 4 ms 6576 KB Output is correct
8 Correct 5 ms 6608 KB Output is correct
9 Correct 4 ms 6480 KB Output is correct
10 Correct 5 ms 6608 KB Output is correct
11 Correct 5 ms 6608 KB Output is correct
12 Correct 4 ms 6608 KB Output is correct
13 Correct 4 ms 6608 KB Output is correct
14 Correct 4 ms 6608 KB Output is correct
15 Correct 5 ms 6608 KB Output is correct
16 Correct 5 ms 6608 KB Output is correct
17 Correct 5 ms 6608 KB Output is correct
18 Correct 5 ms 6608 KB Output is correct
19 Correct 4 ms 6608 KB Output is correct
20 Correct 4 ms 6608 KB Output is correct
21 Incorrect 5 ms 6636 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 630 ms 9876 KB Output is correct
2 Correct 819 ms 13196 KB Output is correct
3 Correct 791 ms 13180 KB Output is correct
4 Correct 951 ms 12608 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 9876 KB Output is correct
2 Correct 819 ms 13196 KB Output is correct
3 Correct 791 ms 13180 KB Output is correct
4 Correct 951 ms 12608 KB Output is correct
5 Correct 630 ms 9936 KB Output is correct
6 Correct 941 ms 13256 KB Output is correct
7 Correct 754 ms 13256 KB Output is correct
8 Correct 834 ms 13256 KB Output is correct
9 Correct 530 ms 6736 KB Output is correct
10 Correct 884 ms 6992 KB Output is correct
11 Correct 983 ms 6992 KB Output is correct
12 Correct 681 ms 6992 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6480 KB Output is correct
2 Correct 5 ms 6608 KB Output is correct
3 Correct 5 ms 6608 KB Output is correct
4 Correct 4 ms 6608 KB Output is correct
5 Correct 4 ms 6608 KB Output is correct
6 Correct 4 ms 6608 KB Output is correct
7 Correct 5 ms 6608 KB Output is correct
8 Correct 5 ms 6608 KB Output is correct
9 Correct 5 ms 6608 KB Output is correct
10 Correct 5 ms 6608 KB Output is correct
11 Correct 4 ms 6608 KB Output is correct
12 Correct 4 ms 6608 KB Output is correct
13 Correct 630 ms 9876 KB Output is correct
14 Correct 819 ms 13196 KB Output is correct
15 Correct 791 ms 13180 KB Output is correct
16 Correct 951 ms 12608 KB Output is correct
17 Correct 630 ms 9936 KB Output is correct
18 Correct 941 ms 13256 KB Output is correct
19 Correct 754 ms 13256 KB Output is correct
20 Correct 834 ms 13256 KB Output is correct
21 Correct 530 ms 6736 KB Output is correct
22 Correct 884 ms 6992 KB Output is correct
23 Correct 983 ms 6992 KB Output is correct
24 Correct 681 ms 6992 KB Output is correct
25 Correct 1002 ms 17808 KB Output is correct
26 Correct 965 ms 17992 KB Output is correct
27 Correct 1022 ms 17992 KB Output is correct
28 Correct 836 ms 17992 KB Output is correct
29 Correct 1010 ms 20504 KB Output is correct
30 Correct 963 ms 20552 KB Output is correct

Subtask #7
0 / 28.0

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