oj.uz

Submission #812585

# Submission time Handle Problem Language Result Execution time Memory
812585 2023-08-07T09:26:10 Z BT21tata Digital Circuit (IOI22_circuit) C++17
18 / 100
 895 ms 13212 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]=(1ll*prv*suff[nw[p]])%MOD;
        return;
    }
    
    for(int u : g[v])
        calc(u, v);
    
    prv=(1ll*prv*g[v].size())%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)
    {
        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]=1ll*suff[i+1]*g[old[i]].size();
        suff[i]%=MOD;
    }
    
    cnt=0;
    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 2 ms 4944 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 3 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 4 ms 5072 KB Output is correct
8 Correct 3 ms 5096 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 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 2 ms 4944 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 3 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 4 ms 5072 KB Output is correct
8 Correct 3 ms 5096 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 3 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 605 ms 9140 KB Output is correct
2 Correct 670 ms 13208 KB Output is correct
3 Correct 665 ms 13200 KB Output is correct
4 Correct 792 ms 13212 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 9140 KB Output is correct
2 Correct 670 ms 13208 KB Output is correct
3 Correct 665 ms 13200 KB Output is correct
4 Correct 792 ms 13212 KB Output is correct
5 Correct 491 ms 9104 KB Output is correct
6 Correct 794 ms 13176 KB Output is correct
7 Correct 895 ms 13160 KB Output is correct
8 Correct 754 ms 13208 KB Output is correct
9 Correct 351 ms 5200 KB Output is correct
10 Correct 765 ms 5456 KB Output is correct
11 Correct 662 ms 5504 KB Output is correct
12 Correct 724 ms 5456 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 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 2 ms 4944 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 3 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 4 ms 5072 KB Output is correct
8 Correct 3 ms 5096 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 3 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 2 ms 4944 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 3 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 4 ms 5072 KB Output is correct
8 Correct 3 ms 5096 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 3 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 -