Submission #971068

#	Time	Username	Problem	Language	Result	Execution time	Memory
971068		ALeonidou	Digital Circuit (IOI22_circuit)	C++17	16 / 100	616 ms	8900 KiB

circuit

#include "circuit.h"
#include <vector>
#include <iostream>
using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define sz(x) (ll)x.size()
#define endl "\n"

typedef vector <int> vi;
typedef pair <ll, ll> ii;
typedef vector <ii> vii;

#define MOD 1000002022
  
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

void printVct(vi &v){
    for (ll i =0; i<sz(v); i++){
      cout<<v[i]<<" ";
    }
    cout<<endl;
}

ll mpow(ll a, ll b){
    if (b == 0) return 1;
    if (b % 2) return (a * (mpow((a*a)%MOD, b/2)% MOD)) % MOD;
    return mpow((a*a)%MOD, b/2)%MOD;
}

#define MID ((l+r)/2)

ll n,m;
vi p,a;
ll dif, ans;

struct node{    //sum seg tree with lazy (base = input gates => base size = m)
    node *L, *R;
    ll val;
    ll lazy;    //0 or 1 => 1 means toggled

    void build (ll l = 0, ll r=m-1){
        lazy = 0;
        if (l == r){
            val = a[l];
        }
        else{
            L = new node, R =new node;
            L->build(l, MID), R->build(MID+1,r);
            val = L->val + R->val;
        }
    }

    ll query(ll tl, ll tr, ll l = 0, ll r =m-1){
        if (tl <= l && r <= tr){
            return val;
        }   
        else if (r < tl || l > tr){
            return 0;
        }
        else{
            propagate(l,r);
            return L->query(tl,tr,l,MID) + R->query(tl,tr,MID+1,r);
        }
    }   

    void update(ll tl, ll tr, ll l = 0, ll r =m-1){
        if (tl <= l && r <= tr){
            ll siz = r-l+1;
            val = siz - val; //all toggled
            lazy = !lazy;
        }    
        else if (r < tl || l > tr){
            return;
        }
        else{
            propagate(l,r);
            L->update(tl,tr,l,MID);
            R->update(tl,tr,MID+1,r);
            val = L->val + R->val;
        }
    }

    void propagate(ll l, ll r){
        if (lazy){
            ll sizL = MID-l+1;
            ll sizR = r-(MID+1)+1;

            L->val = sizL - (L->val);
            R->val = sizR - (R->val);

            L->lazy = !(L->lazy);
            R->lazy = !(R->lazy);
            lazy = 0;
        }
    }
};

node root;
void init(int N, int M, vector <int> P, vector<int> A) {
    n= N, m = M;
    p = P;
    a = A;
    //subtask 4,5:
    ll treeHeight = 0;
    ll p = m;
    while (p){
        p/=2;
        treeHeight++;
    }
    // dbg(treeHeight);
    dif = 1;
    ll p2 = 1;
    // dbg(m-1-treeHeight);
    for (ll i = 0; i<=m-1-treeHeight; i++){
        dif = (dif + p2) % MOD;
        p2 = (p2 * 2) % MOD;
    }
    // dbg(dif);

    //calc ans:
    ll curOff = 0;
    for (ll i = 0; i<m; i++){
        if (!a[i]) curOff++;
    }
    ll all = mpow(2, n);
    ans = (all - ((dif * curOff) % MOD) + MOD) % MOD;
    // dbg(ans);


    //seg tree for sub 5:
    root.build();
}

int count_ways(int L, int R) {
    //subtask 4: L = R
    ll l = L-n, r = R-n;
    ll prevOn = root.val;
    root.update(l,r);
    ll curOn = root.val;

    ll difVal = (((curOn - prevOn + MOD) % MOD) * dif) % MOD;
    ans = (ans + difVal) % MOD;

    return ans;
}

/*

3 4 4
-1 0 0 1 1 2 2
1 1 1 1
4 4
4 4
4 5
4 4

7 8 1
-1 0 0 1 1 2 2 3 3 4 4 5 5 6 6
1 1 1 1 1 1 1 1
10 10




*/












/*

subtask 1:
    ll l = L-n, r = R-n;
    ll curOn = 0;
    for (ll i =0; i<m; i++){
        if (i >= l && i <= r){
            a[i] = !a[i];
        }
        if (a[i]) curOn++;
    }
*/

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