oj.uz

Submission #855582

# Submission time Handle Problem Language Result Execution time Memory
855582 2023-10-01T13:24:42 Z 12345678 Digital Circuit (IOI22_circuit) C++17
25 / 100
 579 ms 22068 KB 
#include "circuit.h"
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
 
const int nx=1e5+5, mod=1e9+2022;
 
int n, m, p[2*nx], sz[2*nx], v[2*nx];
vector<int> d[nx];
 
void dfs(int u)
{
    for (auto v:d[u]) sz[v]=sz[u]+1, dfs(v);
}
 
struct segtree
{
    int d1[4*nx], d2[4*nx];
    bool lz[4*nx];
    void build(int l, int r, int i, vector<int> &t)
    {
        if (l==r) return t[l]?d1[i]=v[l]:d2[i]=v[l], void();
        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 pushlz(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)
    {
        pushlz(l, r, i);
        if (r<ql||qr<l) return;
        if (ql<=l&&r<=qr) return lz[i]=1, pushlz(l, r, i), void();
        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;
    }
} s;
 
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]];
    s.build(0, M-1, 1, A);
}
 
int count_ways(int L, int R) {;
    s.update(0, m-1, 1, L-n, R-n);
    return s.d1[1];
}

Subtask #1
2.0 / 2.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6740 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 2 ms 4692 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6488 KB Output is correct
17 Correct 1 ms 6488 KB Output is correct
18 Correct 1 ms 6488 KB Output is correct
19 Correct 1 ms 6740 KB Output is correct
20 Correct 1 ms 4440 KB Output is correct
21 Incorrect 1 ms 6488 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 379 ms 9040 KB Output is correct
2 Correct 562 ms 11196 KB Output is correct
3 Correct 544 ms 11352 KB Output is correct
4 Correct 551 ms 11216 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 9040 KB Output is correct
2 Correct 562 ms 11196 KB Output is correct
3 Correct 544 ms 11352 KB Output is correct
4 Correct 551 ms 11216 KB Output is correct
5 Correct 470 ms 9040 KB Output is correct
6 Correct 579 ms 11216 KB Output is correct
7 Correct 570 ms 11216 KB Output is correct
8 Correct 541 ms 11228 KB Output is correct
9 Correct 265 ms 4696 KB Output is correct
10 Correct 511 ms 6744 KB Output is correct
11 Correct 485 ms 6744 KB Output is correct
12 Correct 504 ms 4696 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6740 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 2 ms 4692 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 1 ms 6740 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 379 ms 9040 KB Output is correct
14 Correct 562 ms 11196 KB Output is correct
15 Correct 544 ms 11352 KB Output is correct
16 Correct 551 ms 11216 KB Output is correct
17 Correct 470 ms 9040 KB Output is correct
18 Correct 579 ms 11216 KB Output is correct
19 Correct 570 ms 11216 KB Output is correct
20 Correct 541 ms 11228 KB Output is correct
21 Correct 265 ms 4696 KB Output is correct
22 Correct 511 ms 6744 KB Output is correct
23 Correct 485 ms 6744 KB Output is correct
24 Correct 504 ms 4696 KB Output is correct
25 Runtime error 44 ms 22068 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

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