Submission #711341

#	Time	Username	Problem	Language	Result	Execution time	Memory
711341		Jarif_Rahman	Digital Circuit (IOI22_circuit)	C++17	16 / 100	1027 ms	3500 KiB

circuit

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const ll md = 1000002022;

struct segtree{
    struct node{
        int sum = 0, sz = 1;
        bool rev = 0;
        node(){
        }
        node operator+(node X){
            node rt;
            rt.sz = sz+X.sz;
            rt.sum = sum+X.sum;
            return rt;
        }
        void pushdown(node &X){
            if(!rev) return;
            X.rev^=rev;
            X.sum = X.sz-X.sum;
        }
    };
    int k;
    vector<node> v;
    segtree(int n){
        k = 1;
        while(k < n) k*=2;
        v.resize(2*k, node());
        for(int i = k-1; i > 0; i--) v[i] = v[2*i]+v[2*i+1];
    }
    void update(int l, int r, int nd, int a, int b){
        if(a > r || b < l) return;
        if(a >= l && b <= r){
            v[nd].rev^=1;
            v[nd].sum = v[nd].sz-v[nd].sum;
            return;
        }
        int mid = (a+b)/2;
        v[nd].pushdown(v[2*nd]);
        v[nd].pushdown(v[2*nd+1]);
        v[nd].rev = 0;
        update(l, r, 2*nd, a, mid);
        update(l, r, 2*nd+1, mid+1, b);
        v[nd] = v[2*nd]+v[2*nd+1];
    }
    void update(int l, int r){
        update(l, r, 1, 0, k-1);
    }
    int get(){
        return v[1].sum;
    }
};

int n, m;
vector<int> P, A;
segtree s(0);
ll pw = 1;

void init(int _n, int _m, vector<int> _P, vector<int> _A){
    swap(n, _n), swap(m, _m), swap(P, _P), swap(A, _A);
    s = segtree(m);
    for(int i = 0; i < m; i++) if(A[i]) s.update(i, i);
    for(int i = 0; i < n-__builtin_ctz(m); i++) pw*=2, pw%=md;
}

int count_ways(int L, int R){
    s.update(L-n, R-n);
    return (s.get()*pw)%md;
}

• 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