제출 #1134212

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

circuit

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50,mod=1000002022;
inline ll Plus(ll x,ll y){x%=mod;y%=mod;return (x+y)%mod;}
inline ll Puta(ll x,ll y){x%=mod,y%=mod;return (x*y)%mod;}
ll Pow(ll a,ll b){
    ll res=1;
    for(ll x=a;b;x=Puta(x,x),b>>=1) if(b&1) res=Puta(res,x);
    return res;
}
//glupavi mod nije prost
vector<pair<int,int>>faktor[N+50];bool was[N+50];
struct Broj{
    set<pair<int,int>>st;
    Broj(){}
    Broj(int x){
        if(x>1) for(auto i:faktor[x]) st.insert(i);
    }
    void Pomnozi(Broj x){
        for(auto [p,num]:x.st){
            auto lb=st.lower_bound({p,0});
            if(!(lb==st.end()||(*lb).fi!=p)){
                num+=(*lb).se;
                st.erase(lb);
            }
            st.insert({p,num});
        }
    }
    void Podeli(Broj x){
        for(auto [p,num]:x.st){
            auto lb=st.lower_bound({p,0});
            if(lb==st.end()||(*lb).fi!=p) continue;
            num=(*lb).se-num;
            st.erase(lb);
            st.insert({p,num});
        }
    }
    ll Vrednost(){
        ll res=1;
        for(auto [p,num]:st) res=Puta(res,Pow(p,num));
        return res;
    }
};
vector<int>E[2*N];
int a[N],n,m,par[2*N];
ll b[2*N];
Broj val1[2*N],Val1[2*N];
void DFSsetup(int u){
    val1[u]=Broj(E[u].size());
    for(auto i:E[u]){
        Val1[i]=Val1[u];
        Val1[i].Pomnozi(Broj(E[u].size()));
        DFSsetup(i);
        val1[u].Pomnozi(val1[i]);
    }
    if(E[u].empty()) val1[u]=Broj();
}
struct SegTree{
    int root,nc,lc[2*N],rc[2*N];ll sum[2*N],sum1[2*N];bool lazy[2*N];
    void Build(int &c,int ss,int se){
        c=++nc;
        if(ss==se){sum1[c]=b[ss];return;}
        int mid=ss+se>>1;
        Build(lc[c],ss,mid),Build(rc[c],mid+1,se);
        sum1[c]=Plus(sum1[lc[c]],sum1[rc[c]]);
    }
    void update(int c){sum[c]=Plus(sum1[c],mod-sum[c]);lazy[c]^=1;}
    void push(int c){if(!lazy[c])return;update(lc[c]),update(rc[c]),lazy[c]=0;}
    void Update(int c,int ss,int se,int qs,int qe){
        if(qs>qe||qe<ss||se<qs) return;
        if(qs<=ss&&se<=qe){update(c);return;}
        int mid=ss+se>>1;push(c);
        Update(lc[c],ss,mid,qs,qe),Update(rc[c],mid+1,se,qs,qe);
        sum[c]=Plus(sum[lc[c]],sum[rc[c]]);
    }
}ST;
void init(int n1, int m1, std::vector<int> P, std::vector<int> A){
    for(int i=2;i<=N;i++){
        if(!was[i]){
            for(int j=i;j<=N;j+=i){
                was[j]=true;
                int temp=j,num=0;
                while(temp%i==0) temp/=i,num++;
                faktor[j].pb({i,num});
            }
        }
    }
    n=n1,m=m1;
    for(int i=0;i<P.size();i++) par[i]=P[i],E[par[i]].pb(i);
    for(int i=0;i<m;i++) a[i]=A[i];
    DFSsetup(0);
    for(int i=0;i<m;i++){
        int u=i+n;Broj x=val1[0];x.Podeli(Val1[u]);
        b[i]=x.Vrednost();
    }
    ST.Build(ST.root,0,m-1);
    for(int i=0;i<m;i++) if(a[i]==1) ST.Update(ST.root,0,m-1,i,i);
}
int count_ways(int L, int R){
    L-=n,R-=n;
    ST.Update(ST.root,0,m-1,L,R);
    return ST.sum[1];
}

• 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