oj.uz

Submission #681112

# Submission time Handle Problem Language Result Execution time Memory
681112 2023-01-12T11:10:40 Z AngusWong Digital Circuit (IOI22_circuit) C++17
2 / 100
 609 ms 20268 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];
    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 8 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 14416 KB Output is correct
5 Correct 8 ms 14544 KB Output is correct
6 Correct 8 ms 14416 KB Output is correct
7 Correct 9 ms 14416 KB Output is correct
8 Correct 7 ms 14524 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14416 KB Output is correct
2 Incorrect 8 ms 14416 KB 3rd lines differ - on the 1st token, expected: '585825652', found: '-414176370'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.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 14416 KB Output is correct
4 Correct 9 ms 14416 KB Output is correct
5 Correct 8 ms 14544 KB Output is correct
6 Correct 8 ms 14416 KB Output is correct
7 Correct 9 ms 14416 KB Output is correct
8 Correct 7 ms 14524 KB Output is correct
9 Correct 7 ms 14416 KB Output is correct
10 Incorrect 8 ms 14416 KB 3rd lines differ - on the 1st token, expected: '585825652', found: '-414176370'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 609 ms 20268 KB 19065th lines differ - on the 1st token, expected: '991202842', found: '-8799180'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 609 ms 20268 KB 19065th lines differ - on the 1st token, expected: '991202842', found: '-8799180'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14416 KB Output is correct
2 Incorrect 8 ms 14416 KB 3rd lines differ - on the 1st token, expected: '585825652', found: '-414176370'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.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 14416 KB Output is correct
4 Correct 9 ms 14416 KB Output is correct
5 Correct 8 ms 14544 KB Output is correct
6 Correct 8 ms 14416 KB Output is correct
7 Correct 9 ms 14416 KB Output is correct
8 Correct 7 ms 14524 KB Output is correct
9 Correct 7 ms 14416 KB Output is correct
10 Incorrect 8 ms 14416 KB 3rd lines differ - on the 1st token, expected: '585825652', found: '-414176370'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 11.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 14416 KB Output is correct
4 Correct 9 ms 14416 KB Output is correct
5 Correct 8 ms 14544 KB Output is correct
6 Correct 8 ms 14416 KB Output is correct
7 Correct 9 ms 14416 KB Output is correct
8 Correct 7 ms 14524 KB Output is correct
9 Correct 7 ms 14416 KB Output is correct
10 Incorrect 8 ms 14416 KB 3rd lines differ - on the 1st token, expected: '585825652', found: '-414176370'
11 Halted 0 ms 0 KB -