oj.uz

답안 #1057766

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1057766 2024-08-14T05:45:01 Z hirayuu_oj 디지털 회로 (IOI22_circuit) C++17
0 / 100
 3000 ms 1913316 KB 
#include "circuit.h"

#include <vector>

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;

constexpr ll MOD=1'000'002'022;

inline ll safe_mod(ll x,ll p) {
    x%=p;
    if(x<0)x+=p;
    return x;
}

template<typename T,auto op,auto e,typename F,auto mapp,auto comp,auto id>
struct LST {
    vector<T> value;
    vector<F> delay;
    int size;
    explicit LST(int sz):value(sz*2,e()),delay(sz,id()),size(sz){}
    inline T _get(const int pos) {
        return mapp(delay[pos],value[pos]);
    }
    void _delay(const int pos) {
        int k=0;
        int p=pos;
        while(p>1) {
            k++;
            p/=2;
        }
        for(int i=k; i>=1; i--) {
            p=pos>>i;
            value[p]=_get(p);
            delay[p*2]=comp(delay[p],delay[p*2]);
            delay[p*2+1]=comp(delay[p],delay[p*2+1]);
            delay[p]=id();
        }
    }
    void _calc(int pos) {
        pos/=2;
        while(pos>=1) {
            value[pos]=op(_get(pos*2),_get(pos*2+1));
            pos/=2;
        }
    }
    T get(const int pos) {
        return _get(pos+size);
    }
    void set(const int pos,const T val) {
        _delay(pos+size);
        value[pos+size]=val;
        delay[pos+size]=id();
        _calc(pos+size);
    }
    T prod(int lf,int ri) {
        lf+=size;
        ri+=size;
        _delay(lf);
        _delay(ri-1);
        T ret_lf=e(),ret_ri=e();
        while(lf<ri) {
            if(lf&1) {
                ret_lf=op(ret_lf,_get(lf));
                lf++;
            }
            if(ri&1) {
                ri--;
                ret_ri=op(_get(ri),ret_ri);
            }
            lf/=2;
            ri/=2;
        }
        return op(ret_lf,ret_ri);
    }
    void apply(int lf,int ri,F f) {
        lf+=size;
        ri+=size;
        int update_lf=lf;
        int update_ri=ri-1;
        _delay(update_lf);
        _delay(update_ri);
        while(lf<ri) {
            if(lf&1) {
                delay[lf]=comp(f,delay[lf]);
                lf++;
            }
            if(ri&1) {
                ri--;
                delay[ri]=comp(f,delay[ri]);
            }
            lf/=2;
            ri/=2;
        }
        _calc(update_lf);
        _calc(update_ri);
    }
};

template<typename T,auto op,auto e>
struct SegTree {
    vector<T> value;
    int size;
    explicit SegTree(int sz):value(sz*2,e()),size(sz){}
    inline T _get(const int pos) {
        return value[pos];
    }
    void _calc(int pos) {
        pos/=2;
        while(pos>=1) {
            value[pos]=op(_get(pos*2),_get(pos*2+1));
            pos/=2;
        }
    }
    T get(const int pos) {
        return _get(pos+size);
    }
    void set(const int pos,const T val) {
        value[pos+size]=val;
        _calc(pos+size);
    }
    T prod(int lf,int ri) {
        lf+=size;
        ri+=size;
        T ret_lf=e(),ret_ri=e();
        while(lf<ri) {
            if(lf&1) {
                ret_lf=op(ret_lf,_get(lf));
                lf++;
            }
            if(ri&1) {
                ri--;
                ret_ri=op(_get(ri),ret_ri);
            }
            lf/=2;
            ri/=2;
        }
        return op(ret_lf,ret_ri);
    }
};

ll prod_op(const ll x,const ll y) {
    return safe_mod(x*y,MOD);
}
ll prod_e() {
    return 1;
}

pair<ll,ll> op(const pair<ll,ll> x,const pair<ll,ll> y) {
    return {safe_mod(x.first+y.first,MOD),safe_mod(x.second+y.second,MOD)};
}
pair<ll,ll> e() {
    return {0,0};
}
pair<ll,ll> mapp(const bool f,const pair<ll,ll> x) {
    if(f)return {safe_mod(x.second-x.first,MOD),x.second};
    return x;
}
bool comp(const bool f,const bool g) {
    return f!=g;
}
bool id() {
    return false;
}
SegTree<ll,prod_op,prod_e> init_seg(0);
LST<pair<ll,ll>,op,e,bool,mapp,comp,id> seg(0);
vector<vector<int>> tree;
int n,m;
void dfs(int pos) {
    if(n<=pos) {
        seg.set(pos-n,{0,init_seg.prod(0,n)});
    }
    else {
        init_seg.set(pos,1);
        for(int i:tree[pos]) {
            dfs(i);
        }
        init_seg.set(pos,tree[pos].size());
    }
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n=N;
    m=M;
    tree.resize(N+M);
    init_seg=SegTree<ll,prod_op,prod_e>(N);
    seg=LST<pair<ll,ll>,op,e,bool,mapp,comp,id>(M);
    rng(i,1,N+M) {
        tree[P[i]].emplace_back(i);
    }
    rep(i,N) {
        init_seg.set(i,tree[i].size());
    }
    dfs(0);
    rep(i,M) {
        if(A[i]==1)seg.apply(i,i+1,true);
    }
}

int count_ways(int L, int R) {
    seg.apply(L-n,R+1-n,true);
    return seg.prod(0,m).first;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 1 ms 600 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 600 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 1 ms 600 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3136 ms 1913316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3136 ms 1913316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 600 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 1 ms 600 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 1 ms 600 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -