oj.uz

Submission #812477

# Submission time Handle Problem Language Result Execution time Memory
812477 2023-08-07T08:54:46 Z BT21tata Digital Circuit (IOI22_circuit) C++17
18 / 100
 907 ms 13260 KB 
#include "circuit.h"
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
const ll MOD=1e9+2022;
const int N=2e5+5;
 
struct tree
{
    ll one, zero, lazy;
}t[4*N];
 
int nw[N], cnt, old[N], n, m;
ll suff[N], prv=1, a[N];
vector<int>g[N];
 
void dfs(int v)
{
    if(v>=n) return;
    old[cnt]=v;
    nw[v]=cnt++;
    for(int u : g[v])
        dfs(u);
}
 
void calc(int v, int p)
{
    if(v>=n)
    {
        a[v-n]=prv*suff[nw[p]+1];
        a[v-n]%=MOD;
        return;
    }
    
    for(int u : g[v])
        calc(u, v);
    
    prv*=(1ll*g[v].size());
    prv%=MOD;
}
 
void build(int v, int l, int r, vector<int>&state)
{
    if(l==r)
    {
        if(state[l]) t[v]={a[l], 0, 0};
        else t[v]={0, a[l], 0};
        return;
    }
    
    int mid=(l+r)>>1;
    build(v<<1, l, mid, state);
    build(v<<1|1, mid+1, r, state);
 
    t[v]={(t[v<<1].one+t[v<<1|1].one)%MOD, (t[v<<1].zero+t[v<<1|1].zero)%MOD, 0};
}
 
void push(int v, int l, int r)
{
    swap(t[v].zero, t[v].one);
    t[v].lazy=0;
    if(l!=r)
    {
        t[v<<1].lazy^=1;
        t[v<<1|1].lazy^=1;
    }
}
 
void update(int v, int l, int r, int tl, int tr)
{
    if(t[v].lazy) push(v, l, r);
    if(r<tl or tr<l) return;
    if(tl<=l and r<=tr)
    {
        t[v].lazy=1;
        push(v, l, r);
        return;
    }
 
    int mid=(l+r)>>1;
    update(v<<1, l, mid, tl, tr);
    update(v<<1|1, mid+1, r, tl, tr);
 
    t[v]={(t[v<<1].one+t[v<<1|1].one)%MOD, (t[v<<1].zero+t[v<<1|1].zero)%MOD, 0};
}
 
void init(int N, int M, vector<int> p, vector<int> state)
{
    n=N; m=M;
    for(int i=1; i<n+m; i++)
        g[p[i]].push_back(i);
 
    dfs(0);
 
    suff[n]=1;
    for(int i=n-1; i>=0; i--)
    {
        suff[i]=suff[i+1]*g[old[i]].size();
        suff[i]%=MOD;
    }
 
    calc(0, -1);
 
    build(1, 0, m-1, state);
}
 
int count_ways(int l, int r)
{
    update(1, 0, m-1, l-n, r-n);
    return t[1].one;
}

Subtask #1
2.0 / 2.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Correct 2 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 2 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 2 ms 5072 KB Output is correct
14 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
15 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 9116 KB Output is correct
2 Correct 612 ms 13260 KB Output is correct
3 Correct 790 ms 13256 KB Output is correct
4 Correct 672 ms 13212 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 9116 KB Output is correct
2 Correct 612 ms 13260 KB Output is correct
3 Correct 790 ms 13256 KB Output is correct
4 Correct 672 ms 13212 KB Output is correct
5 Correct 448 ms 9124 KB Output is correct
6 Correct 701 ms 13208 KB Output is correct
7 Correct 907 ms 13128 KB Output is correct
8 Correct 656 ms 13216 KB Output is correct
9 Correct 469 ms 5200 KB Output is correct
10 Correct 889 ms 5456 KB Output is correct
11 Correct 699 ms 5456 KB Output is correct
12 Correct 773 ms 5456 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Correct 2 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 2 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 2 ms 5072 KB Output is correct
14 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
15 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Correct 2 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 2 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 2 ms 5072 KB Output is correct
14 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
15 Halted 0 ms 0 KB -