제출 #1057817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057817		hirayuu_oj	디지털 회로 (IOI22_circuit)	C++17	100 / 100	747 ms	20432 KiB

circuit

#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;

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;
    LST(int sz) {
        value.resize(sz*2,e());
        delay.resize(sz*2,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;
        const int update_lf=lf;
        const 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;
    SegTree(int sz) {
        value.resize(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 (x*y)%MOD;
}
ll prod_e() {
    return 1;
}

pair<ll,ll> op(const pair<ll,ll> x,const pair<ll,ll> y) {
    return {x.first+y.first,x.second+y.second};
}
pair<ll,ll> e() {
    return {0,0};
}
pair<ll,ll> mapp(const bool f,const pair<ll,ll> x) {
    if(f)return {x.second-x.first,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) {
        seg.apply(i,i+1,A[i]);
    }
}

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

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11