Submission #825788

#	Time	Username	Problem	Language	Result	Execution time	Memory
825788		becaido	Digital Circuit (IOI22_circuit)	C++17	50 / 100	967 ms	19244 KiB

circuit

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "circuit.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int MOD = 1000002022;
const int SIZE = 2e5 + 5;

int n, m, ans;
vector<int> adj[SIZE];
int a[SIZE], coef[SIZE], all[SIZE], pre[SIZE];

int add(const int &x, const int &y) {
    return x + y >= MOD ? x + y - MOD : x < -y ? x + y + MOD : x + y;
}
int mul(const int &x, const int &y) {
    return 1ll * x * y % MOD;
}

struct Node {
    int sum = 0, lazy = 0;
} node[SIZE * 4];

void build(int pos, int l, int r) {
    if (l == r) {
        if (a[l]) node[pos].sum = coef[l];
        return;
    }
    int mid = (l + r) / 2;
    build(lpos, l, mid);
    build(rpos, mid + 1, r);
    node[pos].sum = add(node[lpos].sum, node[rpos].sum);
}
void push(int pos, int l, int r) {
    if (!node[pos].lazy) return;
    node[pos].sum = add(pre[r], -add((l ? pre[l - 1] : 0), node[pos].sum));
    if (l < r) {
        node[lpos].lazy ^= 1;
        node[rpos].lazy ^= 1;
    }
    node[pos].lazy = 0;
}
void pull(int pos, int l, int r) {
    int mid = (l + r) / 2;
    push(lpos, l, mid);
    push(rpos, mid + 1, r);
    node[pos].sum = add(node[lpos].sum, node[rpos].sum);
}
void upd(int pos, int l, int r, int L, int R) {
    if (l == L && r == R) {
        node[pos].lazy ^= 1;
        return;
    }
    push(pos, L, R);
    int mid = (L + R) / 2;
    if (r <= mid) upd(lpos, l, r, L, mid);
    else if (l > mid) upd(rpos, l, r, mid + 1, R);
    else {
        upd(lpos, l, mid, L, mid);
        upd(rpos, mid + 1, r, mid + 1, R);
    }
    pull(pos, L, R);
}

void dfs0(int pos) {
    int pro = 1;
    for (int np : adj[pos]) {
        dfs0(np);
        pro = mul(pro, all[np]);
    }
    if (adj[pos].size()) pro = mul(pro, adj[pos].size());
    all[pos] = pro;
}
void dfs(int pos, int cur) {
    if (adj[pos].size() == 0) {
        coef[pos - n] = cur;
        return;
    }
    assert(adj[pos].size() == 2);
    dfs(adj[pos][0], mul(cur, all[adj[pos][1]]));
    dfs(adj[pos][1], mul(cur, all[adj[pos][0]]));
}

void init(int N, int M, vector<int> P, vector<int> A) {
    n = N, m = M;
    FOR (i, 1, n + m - 1) adj[P[i]].pb(i);
    dfs0(0);
    dfs(0, 1);
    FOR (i, 0, m - 1) {
        a[i] = A[i];
        pre[i] = add((i ? pre[i - 1] : 0), coef[i]);
    }
    build(1, 0, m - 1);
}

int count_ways(int L, int R) {
    L -= n, R -= n;
    upd(1, L, R, 0, m - 1);
    push(1, 0, m - 1);
    return node[1].sum;
}

/*
in1
3 4 3
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
3 6
out1
2
0
6
*/

#ifdef WAIMAI
int main() {
  int N, M, Q;
  assert(3 == scanf("%d %d %d", &N, &M, &Q));
  vector<int> P(N + M), A(M);
  for (int i = 0; i < N + M; ++i) {
    assert(1 == scanf("%d", &P[i]));
  }
  for (int j = 0; j < M; ++j) {
    assert(1 == scanf("%d", &A[j]));
  }
  init(N, M, P, A);

  for (int i = 0; i < Q; ++i) {
    int L, R;
    assert(2 == scanf("%d %d", &L, &R));
    printf("%d\n", count_ways(L, R));
  }
  return 0;
}
#endif

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