Submission #1167447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167447		SmuggingSpun	디지털 회로 (IOI22_circuit)	C++20	0 / 100	177 ms	2424 KiB

circuit

#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 2e5 + 5;
const int mod =  1000002022;
void add(int& a, int b){
    if((a += b) >= mod){
        a -= mod;
    }
}
int n, m, pw_2[lim], st[lim << 2], a[lim];
bitset<lim << 2>lazy;
void fix(int id, int l, int r, int m){
    st[id] = (1LL * st[id << 1] * st[id << 1 | 1] + 1LL * st[id << 1] * (pw_2[r - m - 1] - st[id << 1 | 1] + mod) + 1LL * st[id << 1 | 1] * (pw_2[m - l] - st[id << 1] + mod)) % mod;
}
void flip(int id, int l, int r){
    st[id] = (pw_2[r - l] - st[id] + mod) % mod;
    lazy.flip(id);
}
void push_down(int id, int l, int r, int m){
    if(lazy.test(id)){
        lazy.reset(id);
        flip(id << 1, l, m);
        flip(id << 1 | 1, m + 1, r);
    }
}
void build(int id, int l, int r){
    if(l == r){
        st[id] = int(a[l] == 1);
        return;
    }
    int m = (l + r) >> 1;
    build(id << 1, l, m);
    build(id << 1 | 1, m + 1, r);
    fix(id, l, r, m);
}
void update(int id, int l, int r, int u, int v){
    if(l > v || r < u){
        return;
    }
    if(u <= l && v >= r){
        flip(id, l, r);
        return;
    }
    int m = (l + r) >> 1;
    push_down(id, l, r, m);
    update(id << 1, l, m, u, v);
    update(id << 1 | 1, m + 1, r, u, v);
    fix(id, l, r, m);
}
void init(int N, int M, vector<int>P, vector<int>A){
    n = N;
    m = M;
    for(int i = 0; i < m; i++){
        a[i] = A[i];
    }
    for(int i = pw_2[0] = 1; i < lim; i++){
        pw_2[i] = (pw_2[i - 1] << 1) % mod;
    }
    lazy.reset();
    build(1, 0, m - 1);
}
int count_ways(int L, int R){
    update(1, 0, m - 1, L, R);
    return st[0];
}

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