oj.uz

Submission #812351

# Submission time Handle Problem Language Result Execution time Memory
812351 2023-08-07T08:28:26 Z BT21tata Digital Circuit (IOI22_circuit) C++17
18 / 100
 939 ms 17908 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], newg[N];
 
void dfs(int v)
{
    if(!g[v].size()) return;
    old[cnt]=v;
    nw[v]=cnt++;
    for(int u : g[v])
        dfs(u);
}
 
void calc(int v, int p)
{
    if(v<n) v=nw[v];
    if(!newg[v].size())
    {
        a[v-n]=prv*suff[p+1];
        a[v-n]%=MOD;
        return;
    }
    
    for(int u : newg[v])
        calc(u, v);
    
    prv*=newg[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);
    
    for(int i=0; i<n; i++)
        swap(newg[i], g[old[i]]);
    suff[n]=1;
    for(int i=n-1; i>=0; i--)
    {
        suff[i]=suff[i+1]*newg[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 4 ms 9680 KB Output is correct
2 Correct 5 ms 9680 KB Output is correct
3 Correct 5 ms 9808 KB Output is correct
4 Correct 5 ms 9712 KB Output is correct
5 Correct 5 ms 9724 KB Output is correct
6 Correct 5 ms 9680 KB Output is correct
7 Correct 4 ms 9804 KB Output is correct
8 Correct 5 ms 9680 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9680 KB Output is correct
2 Correct 5 ms 9716 KB Output is correct
3 Correct 6 ms 9680 KB Output is correct
4 Correct 5 ms 9680 KB Output is correct
5 Correct 4 ms 9680 KB Output is correct
6 Incorrect 7 ms 9808 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 4 ms 9680 KB Output is correct
2 Correct 5 ms 9680 KB Output is correct
3 Correct 5 ms 9808 KB Output is correct
4 Correct 5 ms 9712 KB Output is correct
5 Correct 5 ms 9724 KB Output is correct
6 Correct 5 ms 9680 KB Output is correct
7 Correct 4 ms 9804 KB Output is correct
8 Correct 5 ms 9680 KB Output is correct
9 Correct 4 ms 9680 KB Output is correct
10 Correct 5 ms 9716 KB Output is correct
11 Correct 6 ms 9680 KB Output is correct
12 Correct 5 ms 9680 KB Output is correct
13 Correct 4 ms 9680 KB Output is correct
14 Incorrect 7 ms 9808 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 595 ms 13776 KB Output is correct
2 Correct 760 ms 17872 KB Output is correct
3 Correct 746 ms 17900 KB Output is correct
4 Correct 828 ms 17888 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 13776 KB Output is correct
2 Correct 760 ms 17872 KB Output is correct
3 Correct 746 ms 17900 KB Output is correct
4 Correct 828 ms 17888 KB Output is correct
5 Correct 506 ms 13824 KB Output is correct
6 Correct 741 ms 17908 KB Output is correct
7 Correct 939 ms 17884 KB Output is correct
8 Correct 602 ms 17888 KB Output is correct
9 Correct 497 ms 9936 KB Output is correct
10 Correct 730 ms 10192 KB Output is correct
11 Correct 783 ms 10192 KB Output is correct
12 Correct 696 ms 10192 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9680 KB Output is correct
2 Correct 5 ms 9716 KB Output is correct
3 Correct 6 ms 9680 KB Output is correct
4 Correct 5 ms 9680 KB Output is correct
5 Correct 4 ms 9680 KB Output is correct
6 Incorrect 7 ms 9808 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 4 ms 9680 KB Output is correct
2 Correct 5 ms 9680 KB Output is correct
3 Correct 5 ms 9808 KB Output is correct
4 Correct 5 ms 9712 KB Output is correct
5 Correct 5 ms 9724 KB Output is correct
6 Correct 5 ms 9680 KB Output is correct
7 Correct 4 ms 9804 KB Output is correct
8 Correct 5 ms 9680 KB Output is correct
9 Correct 4 ms 9680 KB Output is correct
10 Correct 5 ms 9716 KB Output is correct
11 Correct 6 ms 9680 KB Output is correct
12 Correct 5 ms 9680 KB Output is correct
13 Correct 4 ms 9680 KB Output is correct
14 Incorrect 7 ms 9808 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 4 ms 9680 KB Output is correct
2 Correct 5 ms 9680 KB Output is correct
3 Correct 5 ms 9808 KB Output is correct
4 Correct 5 ms 9712 KB Output is correct
5 Correct 5 ms 9724 KB Output is correct
6 Correct 5 ms 9680 KB Output is correct
7 Correct 4 ms 9804 KB Output is correct
8 Correct 5 ms 9680 KB Output is correct
9 Correct 4 ms 9680 KB Output is correct
10 Correct 5 ms 9716 KB Output is correct
11 Correct 6 ms 9680 KB Output is correct
12 Correct 5 ms 9680 KB Output is correct
13 Correct 4 ms 9680 KB Output is correct
14 Incorrect 7 ms 9808 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
15 Halted 0 ms 0 KB -