제출 #720667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720667		Mamedov	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1161 ms	18588 KiB

circuit

#include "circuit.h"
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

const int mod = 1e9 + 2022;
const int up = 1e5 + 5;
vvi tree;
vi reNum, realNode, suff;
vi cont, psum;

int n, m;

int tme = 0;
void dfs1(int v) {
  if (v < n) {
    reNum[v] = tme;
    realNode[tme] = v;
    tme++;
  }
  for (int to : tree[v]) {
    dfs1(to);
  }
}

int pre = 1, tmr = 0;
void dfs2(int v) {
  if (v >= n) {
    cont[v - n] = (1ll * pre * suff[tmr]) % mod;
  } else {
    tmr++;
  }
  for (int to : tree[v]) {
    dfs2(to);
  }
  if (v < n) {
    pre = (1ll * pre * size(tree[v])) % mod;
  }
}

int segTree[up << 2];
int lazy[up << 2];

void build(int v, int l, int r, vi &A) {
  if (l == r) {
    segTree[v] = A[l] * cont[l];
  } else {
    int mid = (l + r) >> 1;
    build(v << 1, l, mid , A);
    build((v << 1) | 1, mid + 1, r, A);
    segTree[v] = (segTree[v << 1] + segTree[(v << 1) | 1]) % mod;
  }
}

void relax(int v, int l, int r) {
  lazy[v] = 0;
  int total = psum[r + 1] - psum[l];
  if (total < 0) total += mod;
  segTree[v] = total - segTree[v];
  if (segTree[v] < 0) segTree[v] += mod;

  if (l != r) {
    lazy[v << 1] ^= 1;
    lazy[(v << 1) | 1] ^= 1;
  }
}
void update(int v, int l, int r, int ul, int ur) {
  if (lazy[v]) relax(v, l, r);
  if (r < ul || ur < l) return;
  if (ul <= l && r <= ur) {
    relax(v, l, r);
  } else {
    int mid = (l + r) >> 1;
    update(v << 1, l, mid, ul, ur);
    update((v << 1) | 1, mid + 1, r, ul, ur);
    segTree[v] = (segTree[v << 1] + segTree[(v << 1) | 1]) % mod;
  }
}

void init(int N, int M, vi P, vi A) {
  n = N; m = M;
  tree.resize(N + M);
  for (int i = 1; i < N + M; ++i) {
    tree[P[i]].eb(i);
  }

  reNum.resize(N);
  realNode.resize(N);
  dfs1(0);

  suff.resize(N + 1);
  suff[N] = 1;
  for (int i = N - 1; i >= 0; --i) {
    suff[i] = (1ll * suff[i + 1] * size(tree[realNode[i]])) % mod;
  }

  cont.resize(M);
  dfs2(0);
  psum.resize(M + 1);
  psum[0] = 0;
  for (int i = 0; i < M; ++i) {
    psum[i + 1] = psum[i] + cont[i];
    if (psum[i + 1] >= mod) psum[i + 1] -= mod;
  }
  build(1, 0, M - 1, A);
}

int count_ways(int L, int R) {
  update(1, 0, m - 1, L - n, R - n);
  return segTree[1];
}

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