oj.uz

Submission #681113

# Submission time Handle Problem Language Result Execution time Memory
681113 2023-01-12T11:11:27 Z AngusWong Digital Circuit (IOI22_circuit) C++17
62 / 100
 1218 ms 32304 KB 
#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
using namespace std;

const ll mod=1e9+2022;
const ll N=2e5+9;
ll n, m, a[N], pw[N], cnt[N], ps[N], seg[N], lazy[N], ans=0;
vector<ll> v[N], pre[N], suf[N];

void dfs(ll x){
    if (x>=n){
        pw[x]=1;
        return;
    }
    pw[x]=v[x].size();
    for (ll i: v[x]){
        dfs(i);
        pw[x]=pw[x]*pw[i]%mod;
    }
}

void dfs2(ll x, ll now=1){
    if (x>=n){
        cnt[x-n+1]=ps[x-n+1]=now;
        return;
    }
    ll sz=v[x].size();
    pre[x].resize(sz);
    pre[x][0]=pw[v[x][0]];
    for (int i=1; i<sz; i++) pre[x][i]=pre[x][i-1]*pw[v[x][i]]%mod;
    suf[x].resize(sz);
    suf[x][sz-1]=pw[v[x][sz-1]];
    for (int i=sz-2; i>=0; i--) suf[x][i]=suf[x][i+1]*pw[v[x][i]]%mod;
    for (int i=0; i<sz; i++){
        ll tmp=now;
        if (i) tmp=tmp*pre[x][i-1]%mod;
        if (i<sz-1) tmp=tmp*suf[x][i+1]%mod;
        dfs2(v[x][i], tmp);
    }
}

void push(ll id, ll x, ll y){
    if (!lazy[id]) return;
    lazy[id]=0;
    seg[id]=((ps[y]-ps[x-1]-seg[id])%mod+mod)%mod;
    if (x!=y){
        lazy[id*2]^=1;
        lazy[id*2+1]^=1;
    }
}

void build(ll id=1, ll x=1, ll y=m){
    if (x==y){
        seg[id]=cnt[x]*a[x];
        lazy[id]=0;
        return;
    }
    ll mid=(x+y)/2;
    build(id*2, x, mid);
    build(id*2+1, mid+1, y);
    seg[id]=(seg[id*2]+seg[id*2+1])%mod;
}

void update(ll l, ll r, ll id=1, ll x=1, ll y=m){
    push(id, x, y);
    if (l<=x && y<=r){
        lazy[id]^=1;
        push(id, x, y);
        return;
    }
    if (l>y || r<x) return;
    ll mid=(x+y)/2;
    update(l, r, id*2, x, mid);
    update(l, r, id*2+1, mid+1, y);
    seg[id]=(seg[id*2]+seg[id*2+1])%mod;
}

ll qry(ll p, ll id=1, ll x=1, ll y=m){
    push(id, x, y);
    if (x==y) return seg[id];
    ll mid=(x+y)/2;
    if (p<=mid) return qry(p, id*2, x, mid);
    return qry(p, id*2+1, mid+1, y);
}

void init(int N, int M, vector<int> P, vector<int> A){
    n=N, m=M;
    for (int i=1; i<n+m; i++) v[P[i]].push_back(i);
    for (int i=0; i<m; i++) a[i+1]=A[i];
    dfs(0);
    dfs2(0);
    for (int i=2; i<=m; i++) ps[i]=(ps[i]+ps[i-1])%mod;
    build();
}

int count_ways(int L, int R){
    update(L-n+1, R-n+1);
    push(1, 1, m);
    return seg[1];
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14416 KB Output is correct
2 Correct 8 ms 14416 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 9 ms 14460 KB Output is correct
5 Correct 8 ms 14416 KB Output is correct
6 Correct 8 ms 14452 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 8 ms 14416 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14416 KB Output is correct
2 Correct 8 ms 14416 KB Output is correct
3 Correct 8 ms 14516 KB Output is correct
4 Correct 8 ms 14516 KB Output is correct
5 Correct 10 ms 14416 KB Output is correct
6 Correct 8 ms 14544 KB Output is correct
7 Correct 11 ms 14544 KB Output is correct
8 Correct 8 ms 14532 KB Output is correct
9 Correct 11 ms 14544 KB Output is correct
10 Correct 8 ms 14644 KB Output is correct
11 Correct 10 ms 14592 KB Output is correct
12 Correct 8 ms 14544 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14416 KB Output is correct
2 Correct 8 ms 14416 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 9 ms 14460 KB Output is correct
5 Correct 8 ms 14416 KB Output is correct
6 Correct 8 ms 14452 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 8 ms 14416 KB Output is correct
9 Correct 8 ms 14416 KB Output is correct
10 Correct 8 ms 14416 KB Output is correct
11 Correct 8 ms 14516 KB Output is correct
12 Correct 8 ms 14516 KB Output is correct
13 Correct 10 ms 14416 KB Output is correct
14 Correct 8 ms 14544 KB Output is correct
15 Correct 11 ms 14544 KB Output is correct
16 Correct 8 ms 14532 KB Output is correct
17 Correct 11 ms 14544 KB Output is correct
18 Correct 8 ms 14644 KB Output is correct
19 Correct 10 ms 14592 KB Output is correct
20 Correct 8 ms 14544 KB Output is correct
21 Correct 8 ms 14544 KB Output is correct
22 Correct 9 ms 14544 KB Output is correct
23 Correct 7 ms 14544 KB Output is correct
24 Correct 10 ms 14624 KB Output is correct
25 Correct 8 ms 14516 KB Output is correct
26 Correct 8 ms 14544 KB Output is correct
27 Correct 8 ms 14544 KB Output is correct
28 Correct 9 ms 14600 KB Output is correct
29 Correct 9 ms 14416 KB Output is correct
30 Correct 8 ms 14416 KB Output is correct
31 Correct 11 ms 14544 KB Output is correct
32 Correct 9 ms 14544 KB Output is correct
33 Correct 8 ms 14544 KB Output is correct
34 Correct 8 ms 14544 KB Output is correct
35 Correct 8 ms 14416 KB Output is correct
36 Correct 8 ms 14672 KB Output is correct
37 Correct 8 ms 14672 KB Output is correct
38 Correct 9 ms 14672 KB Output is correct
39 Correct 8 ms 14544 KB Output is correct
40 Correct 8 ms 14544 KB Output is correct
41 Correct 9 ms 14544 KB Output is correct
42 Correct 8 ms 14416 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 20244 KB Output is correct
2 Correct 1031 ms 26156 KB Output is correct
3 Correct 1018 ms 26212 KB Output is correct
4 Correct 975 ms 26184 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 20244 KB Output is correct
2 Correct 1031 ms 26156 KB Output is correct
3 Correct 1018 ms 26212 KB Output is correct
4 Correct 975 ms 26184 KB Output is correct
5 Correct 634 ms 20304 KB Output is correct
6 Correct 1112 ms 26172 KB Output is correct
7 Correct 1218 ms 26200 KB Output is correct
8 Correct 1022 ms 26168 KB Output is correct
9 Correct 421 ms 14776 KB Output is correct
10 Correct 979 ms 15140 KB Output is correct
11 Correct 959 ms 15080 KB Output is correct
12 Correct 946 ms 15084 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14416 KB Output is correct
2 Correct 8 ms 14416 KB Output is correct
3 Correct 8 ms 14516 KB Output is correct
4 Correct 8 ms 14516 KB Output is correct
5 Correct 10 ms 14416 KB Output is correct
6 Correct 8 ms 14544 KB Output is correct
7 Correct 11 ms 14544 KB Output is correct
8 Correct 8 ms 14532 KB Output is correct
9 Correct 11 ms 14544 KB Output is correct
10 Correct 8 ms 14644 KB Output is correct
11 Correct 10 ms 14592 KB Output is correct
12 Correct 8 ms 14544 KB Output is correct
13 Correct 635 ms 20244 KB Output is correct
14 Correct 1031 ms 26156 KB Output is correct
15 Correct 1018 ms 26212 KB Output is correct
16 Correct 975 ms 26184 KB Output is correct
17 Correct 634 ms 20304 KB Output is correct
18 Correct 1112 ms 26172 KB Output is correct
19 Correct 1218 ms 26200 KB Output is correct
20 Correct 1022 ms 26168 KB Output is correct
21 Correct 421 ms 14776 KB Output is correct
22 Correct 979 ms 15140 KB Output is correct
23 Correct 959 ms 15080 KB Output is correct
24 Correct 946 ms 15084 KB Output is correct
25 Incorrect 1008 ms 32304 KB 1st lines differ - on the 1st token, expected: '732332002', found: '401339960'
26 Halted 0 ms 0 KB -

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14416 KB Output is correct
2 Correct 8 ms 14416 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 9 ms 14460 KB Output is correct
5 Correct 8 ms 14416 KB Output is correct
6 Correct 8 ms 14452 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 8 ms 14416 KB Output is correct
9 Correct 8 ms 14416 KB Output is correct
10 Correct 8 ms 14416 KB Output is correct
11 Correct 8 ms 14516 KB Output is correct
12 Correct 8 ms 14516 KB Output is correct
13 Correct 10 ms 14416 KB Output is correct
14 Correct 8 ms 14544 KB Output is correct
15 Correct 11 ms 14544 KB Output is correct
16 Correct 8 ms 14532 KB Output is correct
17 Correct 11 ms 14544 KB Output is correct
18 Correct 8 ms 14644 KB Output is correct
19 Correct 10 ms 14592 KB Output is correct
20 Correct 8 ms 14544 KB Output is correct
21 Correct 8 ms 14544 KB Output is correct
22 Correct 9 ms 14544 KB Output is correct
23 Correct 7 ms 14544 KB Output is correct
24 Correct 10 ms 14624 KB Output is correct
25 Correct 8 ms 14516 KB Output is correct
26 Correct 8 ms 14544 KB Output is correct
27 Correct 8 ms 14544 KB Output is correct
28 Correct 9 ms 14600 KB Output is correct
29 Correct 9 ms 14416 KB Output is correct
30 Correct 8 ms 14416 KB Output is correct
31 Correct 11 ms 14544 KB Output is correct
32 Correct 9 ms 14544 KB Output is correct
33 Correct 8 ms 14544 KB Output is correct
34 Correct 8 ms 14544 KB Output is correct
35 Correct 8 ms 14416 KB Output is correct
36 Correct 8 ms 14672 KB Output is correct
37 Correct 8 ms 14672 KB Output is correct
38 Correct 9 ms 14672 KB Output is correct
39 Correct 8 ms 14544 KB Output is correct
40 Correct 8 ms 14544 KB Output is correct
41 Correct 9 ms 14544 KB Output is correct
42 Correct 8 ms 14416 KB Output is correct
43 Correct 484 ms 15032 KB Output is correct
44 Correct 759 ms 15004 KB Output is correct
45 Correct 829 ms 15068 KB Output is correct
46 Correct 881 ms 15424 KB Output is correct
47 Correct 642 ms 15516 KB Output is correct
48 Correct 628 ms 15472 KB Output is correct
49 Correct 685 ms 15464 KB Output is correct
50 Correct 746 ms 15440 KB Output is correct
51 Correct 840 ms 15028 KB Output is correct
52 Correct 865 ms 15056 KB Output is correct
53 Correct 837 ms 15396 KB Output is correct
54 Correct 786 ms 15380 KB Output is correct
55 Correct 903 ms 15160 KB Output is correct
56 Correct 858 ms 15040 KB Output is correct
57 Correct 896 ms 15028 KB Output is correct
58 Correct 750 ms 15848 KB Output is correct
59 Correct 887 ms 16044 KB Output is correct
60 Correct 1049 ms 16032 KB Output is correct
61 Correct 1002 ms 15152 KB Output is correct
62 Correct 1097 ms 14896 KB Output is correct
63 Correct 800 ms 14948 KB Output is correct
64 Correct 1028 ms 14940 KB Output is correct
65 Correct 369 ms 14800 KB Output is correct
66 Correct 1178 ms 15156 KB Output is correct
67 Correct 810 ms 15188 KB Output is correct
68 Correct 831 ms 15184 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14416 KB Output is correct
2 Correct 8 ms 14416 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 9 ms 14460 KB Output is correct
5 Correct 8 ms 14416 KB Output is correct
6 Correct 8 ms 14452 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 8 ms 14416 KB Output is correct
9 Correct 8 ms 14416 KB Output is correct
10 Correct 8 ms 14416 KB Output is correct
11 Correct 8 ms 14516 KB Output is correct
12 Correct 8 ms 14516 KB Output is correct
13 Correct 10 ms 14416 KB Output is correct
14 Correct 8 ms 14544 KB Output is correct
15 Correct 11 ms 14544 KB Output is correct
16 Correct 8 ms 14532 KB Output is correct
17 Correct 11 ms 14544 KB Output is correct
18 Correct 8 ms 14644 KB Output is correct
19 Correct 10 ms 14592 KB Output is correct
20 Correct 8 ms 14544 KB Output is correct
21 Correct 8 ms 14544 KB Output is correct
22 Correct 9 ms 14544 KB Output is correct
23 Correct 7 ms 14544 KB Output is correct
24 Correct 10 ms 14624 KB Output is correct
25 Correct 8 ms 14516 KB Output is correct
26 Correct 8 ms 14544 KB Output is correct
27 Correct 8 ms 14544 KB Output is correct
28 Correct 9 ms 14600 KB Output is correct
29 Correct 9 ms 14416 KB Output is correct
30 Correct 8 ms 14416 KB Output is correct
31 Correct 11 ms 14544 KB Output is correct
32 Correct 9 ms 14544 KB Output is correct
33 Correct 8 ms 14544 KB Output is correct
34 Correct 8 ms 14544 KB Output is correct
35 Correct 8 ms 14416 KB Output is correct
36 Correct 8 ms 14672 KB Output is correct
37 Correct 8 ms 14672 KB Output is correct
38 Correct 9 ms 14672 KB Output is correct
39 Correct 8 ms 14544 KB Output is correct
40 Correct 8 ms 14544 KB Output is correct
41 Correct 9 ms 14544 KB Output is correct
42 Correct 8 ms 14416 KB Output is correct
43 Correct 635 ms 20244 KB Output is correct
44 Correct 1031 ms 26156 KB Output is correct
45 Correct 1018 ms 26212 KB Output is correct
46 Correct 975 ms 26184 KB Output is correct
47 Correct 634 ms 20304 KB Output is correct
48 Correct 1112 ms 26172 KB Output is correct
49 Correct 1218 ms 26200 KB Output is correct
50 Correct 1022 ms 26168 KB Output is correct
51 Correct 421 ms 14776 KB Output is correct
52 Correct 979 ms 15140 KB Output is correct
53 Correct 959 ms 15080 KB Output is correct
54 Correct 946 ms 15084 KB Output is correct
55 Incorrect 1008 ms 32304 KB 1st lines differ - on the 1st token, expected: '732332002', found: '401339960'
56 Halted 0 ms 0 KB -