Submission #1070364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070364		Mihailo	Digital Circuit (IOI22_circuit)	C++17	4 / 100	777 ms	19904 KiB

circuit

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pll pair<long long, long long>
#define MOD 1000002022ll
#define xx first
#define yy second
using namespace std;
typedef long long ll;

struct node {
    ll l, r, sum;
    bool flip;
    node *left, *right;
    node(ll l, ll r): l(l), r(r), sum(0), flip(false), left(nullptr), right(nullptr) {};
};

vector<ll> p, prd, w, cmw, makew;
vector<vector<ll>> ch;
ll pref[200200], n;
node *tree;

ll zbir(ll l, ll r) {
    return (pref[r]-(l==0?0:pref[l-1])+MOD)%MOD;
}

void flip(node *cur) {
    if(cur==nullptr) return;
    cur->flip=!cur->flip;
    cur->sum=zbir(cur->l, cur->r)-cur->sum;
}

void flipprop(node *cur) {
    if(cur->flip) {
        cur->flip=false;
        flip(cur->left);
        flip(cur->right);
    }
}

void fix(node *cur) {
    if(cur->l!=cur->r) {
        flipprop(cur->left);
        flipprop(cur->right);
        cur->sum=(cur->left->sum+cur->right->sum)%MOD;
    }
}

node *build(ll l, ll r) {
    node *cur=new node(l, r);
    if(l!=r) {
        ll m=(l+r)/2;
        cur->left=build(l, m);
        cur->right=build(m+1, r);
    }
    return cur;
}

void flipi(node *cur, ll l, ll r) {
    //cout<<l<<' '<<r<<"   "<<cur->l<<' '<<cur->r<<'\n';
    if(l>r) return;
    if(cur->l==l&&cur->r==r) {
        flip(cur);
        return;
    }
    flipi(cur->left, l, min(r, cur->left->r));
    flipi(cur->right, max(l, cur->right->l), r);
    fix(cur);
    //cout<<cur->l<<' '<<cur->r<<' '<<cur->sum<<'\n';
}

ll saberisve() {
    return tree->sum;
}

void solvew(ll l, ll r, ll mul) {
    if(l>r) exit(-1);
    if(l!=r) {
        ll m=(l+r)/2;
        ll nml=mul;
        for(ll i=l; i<=m; i++) {
            nml*=prd[makew[i]];
            nml%=MOD;
        }
        solvew(m+1, r, nml);
        nml=mul;
        for(ll i=m+1; i<=r; i++) {
            nml*=prd[makew[i]];
            nml%=MOD;
        }
        solvew(l, m, nml);
        return;
    }
    w[makew[l]]=mul;
}

void init(int N, int M, vector<int> P, vector<int> A) {
    n=N;
    for(auto i:P) ch.pb(p);
    for(auto i:P) {
        p.pb(i);
        if(i>=0) ch[i].pb(p.size()-1);
        prd.pb(1);
        w.pb(1);
        cmw.pb(1);
    }
    for(ll i=N-1; i>=0; i--) {
        prd[i]=ch[i].size();
        for(ll j:ch[i]) {
            prd[i]*=prd[j];
            prd[i]%=MOD;
        }
    }
    for(ll i=N-1; i>=0; i--) {
        makew=ch[i];
        solvew(0, makew.size()-1, 1);
    }
    for(int i=1; i<N+M; i++) {
        cmw[i]=w[i]*cmw[p[i]];
        cmw[i]%=MOD;
    }
    pref[0]=cmw[N];
    for(int i=1; i<M; i++) {
        pref[i]=pref[i-1]+cmw[N+i];
        pref[i]%=MOD;
    }
    tree=build(0, M-1);
    for(int i=0; i<M; i++) {
        //cout<<i<<'\n';
        if(A[i]) flipi(tree, i, i);
    }
    //for(ll i=0; i<N+M; i++) cout<<prd[i]<<' '<<w[i]<<'\n';
}

int count_ways(int L, int R) {
    flipi(tree, L-n, R-n);
    return saberisve();
}

Compilation message (stderr)

circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:99:14: warning: unused variable 'i' [-Wunused-variable]
   99 |     for(auto i:P) ch.pb(p);
      |              ^

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