Submission #628102

#	Time	Username	Problem	Language	Result	Execution time	Memory
628102		MarkBcc168	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1124 ms	24776 KiB

circuit

#include <bits/stdc++.h>
using namespace std;
#define ll long long

vector<ll> p_sum(100005,0), w(100005,0);

const ll mod = 1e9+2022;

struct Node{
    Node *l_child, *r_child;
    int l,r; ll sum; bool lazy;
    Node(){}
    Node(int _l, int _r){
        l = _l; r = _r; sum=0; lazy = false;
        int m = (l+r)/2;
        if(r-l > 1){
            l_child = new Node(l,m);
            r_child = new Node(m,r);
        }
        //cout << l << " " << r << "\n";
    }
    void push(){
        if(!lazy) return;
        if(r-l==1){
            lazy = false;
            sum = w[l] - sum;
        }
        else{
            lazy = false;
            l_child->flip(l,r);
            r_child->flip(l,r);
        }
    }
    void flip(int L, int R){
        if(R <= l || L >= r) return; //not intersect
        else if(r-l == 1){
            sum = w[l] - sum;
        }
        else if(L <= l && r <= R){ //completely within
            lazy = !lazy;
            sum = (p_sum[r] - p_sum[l] - sum + 2*mod);
            while(sum >= mod) sum -= mod;
        }
        else{
            push();
            l_child->flip(L,R); r_child->flip(L,R);
            sum = ((l_child->sum) + (r_child->sum));
            if(sum >= mod) sum -= mod;
        }
    }
    ll query(){
        push(); return sum;
    }
};

ll exp(ll a, ll n){
    if(n==0) return 1;
    if(n==1) return a%mod;
    ll x = exp(a, n/2);
    if(n%2==0) return (x*x)%mod;
    else return (((x*x)%mod)*a)%mod;
} 

const ll p = 2;
const ll q = 223;
const ll r = 2242157;
const ll phi = (p-1)*(q-1)*(r-1);

struct mint{
    int vp, vq; ll n;
    mint(ll _n){
        vp = 0; vq = 0;
        n = _n;
        while(n%p==0){vp++; n/=p;}
        while(n%q==0){vq++; n/=q;}
        n = n%mod;
    }
    mint(int _vp, int _vq, ll _n){
        vp = _vp; vq = _vq; n = _n%mod;
    }
    friend mint operator *(mint a, mint b){
        return mint(a.vp+b.vp, a.vq+b.vq, a.n*b.n);
    }
    mint inv(){
        return mint(-vp, -vq, exp(n,phi-1));
    }
    friend mint operator /(mint a, mint b){
        return a * b.inv();
    }
    ll to_int(){
        assert(vp >= 0 && vq >= 0);
        ll m=n;
        m = (m*exp(p,vp)) % mod;
        m = (m*exp(q,vq)) % mod;
        return m;
    }
};

int n,m;
Node tr(0,100005);

void init(int _n, int _m, std::vector<int> p, std::vector<int> a){
    n = _n; m = _m;
    //step 1: compute degree
    vector<int> adj[n];
    vector<int> d(n,0);
    vector<mint> d_mod(n,1);
    mint prod(1);
    for(int i=1; i<n+m; ++i){
        adj[p[i]].push_back(i);
        d[p[i]]++;
    }
    for(int i=0; i<n; ++i){
        d_mod[i] = mint(d[i]);
        prod = prod * d_mod[i];
    }
    //step 2: dfs to find weight of each leaf
    vector<mint> node_w(n+m, mint(1));
    node_w[0] = prod;

    vector<int> st(1,0);
    while(!st.empty()){
        int v = st[st.size()-1];
        st.pop_back();
        //cout << v << "\n";
        for(int u : adj[v]){
            node_w[u] = node_w[v] / d_mod[v];
            if(u < n) st.push_back(u);
        }
    }
    //step 3: build the tree
    p_sum[0] = 0;
    for(int i=0; i<m; ++i){
        w[i] = node_w[i+n].to_int();
        p_sum[i+1] = (p_sum[i] + w[i]);
        if(p_sum[i+1] >= mod) p_sum[i+1] -= mod;
    }
    for(int i=0; i<m; ++i){
        if(a[i] == 1) tr.flip(i,i+1);
    }
}
int count_ways(int l, int r){
    tr.flip(l-n,r-n+1);
    return tr.query();
}


/*int main(){
    for(int i=0; i<100; ++i){
        w[i] = i;
        p_sum[i+1] = p_sum[i] + w[i];
    }
    tr.flip(3,6);
    cout << tr.query() << "\n";
    tr.flip(5,10);
    cout << tr.query() << "\n";
}*/

• 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