Submission #636061

#	Time	Username	Problem	Language	Result	Execution time	Memory
636061		k_balint31415	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1372 ms	32460 KiB

circuit

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1000002022; //2*223*2242157
const ll mod=2242157;
const ll phi=497758632;
const int c=2e5+5;

struct num{
    ll _2,_223,_rest;
};

ll power(ll a, ll b, ll m){
    ll res=1;
    while(b){
        if(b&1){
            res*=a;
            res%=m;
        }
        a*=a; a%=m; b>>=1;
    }
    return res;
}

num div(num a, num b){
    num res;
    res._2=a._2-b._2;
    res._223=a._223-b._223;
    res._rest=a._rest*power(b._rest,phi-1,MOD)%MOD;
    return res;
}

num mul(num a, num b){
    num res;
    res._2=a._2+b._2;
    res._223=a._223+b._223;
    res._rest=a._rest*b._rest%MOD;
    return res;
}

num valt(ll a){
    num res;
    res._2=0;
    while(a%2==0){
        ++res._2; a/=2;
    }
    res._223=0;
    while(a%223==0){
        ++res._223; a/=223;
    }
    res._rest=a%MOD;
    return res;
}

ll vissza(num a){
    return power(2,a._2,MOD)*power(223,a._223,MOD)%MOD*a._rest%MOD;
}

int n,m;
vector<int> adj[c];
num db[c];
num arr[c];
num all;
bool szin[c];
int _N,_M;

void dfs(int v, num cur){
    db[v]=cur;
    cur=div(cur,arr[v]);
    for(int x: adj[v]){
        dfs(x,cur);
    }
}

pair<ll,ll> add(pair<ll,ll> a, pair<ll,ll> b){
    return make_pair((a.first+b.first)%MOD,(a.second+b.second)%MOD);
}

pair<ll,ll> tree[4*c];
bool lazy[4*c];

void build(int v, int l, int r){
    if(l==r){
        //cout << l << ' ' << vissza(db[l+_N-1]) << endl;
        if(!szin[l+_N-1]) tree[v]=make_pair(vissza(db[l+_N-1]),0);
        else tree[v]=make_pair(0,vissza(db[l+_N-1]));
        return;
    }

    int mid=l+r>>1;
    build(2*v,l,mid); build(2*v+1,mid+1,r);
    tree[v]=add(tree[2*v],tree[2*v+1]);
}

void update(int v, int l, int r, int x, int y){
    if(lazy[v]){
        swap(tree[v].first,tree[v].second);
        if(l != r){
            lazy[2*v]=lazy[2*v]^1;
            lazy[2*v+1]=lazy[2*v+1]^1;
        }
        lazy[v]=0;
    }

    if(l>r || l>y || x>r || x>y) return;

    if(x<=l && r<=y){
        swap(tree[v].first,tree[v].second);
        if(l != r){
            lazy[2*v]=lazy[2*v]^1;
            lazy[2*v+1]=lazy[2*v+1]^1;
        }
        return;
    }

    int mid=l+r>>1;
    update(2*v,l,mid,x,y); update(2*v+1,mid+1,r,x,y);
    tree[v]=add(tree[2*v],tree[2*v+1]);
}

void init(int N, int M, vector<int> P, vector<int> A){
    int n=N+M;
    _N=N; _M=M;
    all._2=0; all._223=0; all._rest=1;
    for(int i=1;i<n;i++){
        if(i>=N) szin[i]=A[i-N];
        adj[P[i]].push_back(i);
    }


    for(int i=0;i<n;i++){
        if(i<N){
            arr[i]=valt(adj[i].size());
            all=mul(all,arr[i]);
        }
        else arr[i]=valt(1);
    }

    dfs(0,all);
    
    build(1,1,M);
}

int count_ways(int L, int R){
    update(1,1,_M,L-_N+1,R-_N+1);
    return tree[1].second;
}

/*int main(){
    init(3,4,{-1, 0, 1, 2, 1, 1, 0},{1, 0, 1, 0});
    cout << count_ways(3,4) << '\n';
    cout << count_ways(4,5) << '\n';
    cout << count_ways(3,6) << endl;
}*/

Compilation message (stderr)

circuit.cpp: In function 'void build(int, int, int)':
circuit.cpp:90:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |     int mid=l+r>>1;
      |             ~^~
circuit.cpp: In function 'void update(int, int, int, int, int)':
circuit.cpp:116:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |     int mid=l+r>>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