제출 #1207088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1207088		belgianbot	Digital Circuit (IOI22_circuit)	C++20	16 / 100	383 ms	6108 KiB

circuit

#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;

const int MOD = 1000002022;
const int LOG = 26;

vector<int> ans;
struct light {
  long long on, off;
};

light merge(light a, light b) {
  light res;
  res.on = (((a.on * b.off) % MOD + (a.off * b.on) % MOD) % MOD + (2*a.on * b.on) % MOD) %MOD;
  res.off = (((a.off * b.on) % MOD + (a.on * b.off) % MOD) % MOD + (2*a.off * b.off) % MOD) %MOD;
  return res;
}
struct segTree {
  vector<light> t;
  vector<bool> lazy;

  void propagate(int i, int l, int r) {
    if (!lazy[i]) return;
    swap(t[i].on, t[i].off);
    if (l != r) {
      lazy[2*i] = !lazy[2*i];
      lazy[2*i+1] = !lazy[2*i+1];
    }
    lazy[i] = false;
  }
  void init(int sz) {
    t.resize(4*sz);
    lazy.resize(4*sz, false);
  }
  void updt(int i) {
    t[i] = merge(t[i*2], t[i*2+1]);
  }
  void build(int i, int l, int r, vector<int> &v) {
    if (l==r) {
      if (v[l]) {
        t[i].on = 1;
        t[i].off = 0;
      } else {
        t[i].off = 1;
        t[i].on = 0;
      }
      return;
    }
    int mid = (l+r)/2;
    build(2*i, l, mid, v);
    build(2*i+1, mid+1, r, v);
    updt(i);
  }
  void update(int i, int l, int r, int qL, int qR) {
    propagate(i, l, r);
    if (qR < l || qL > r) return;
    if (qL <= l && qR >= r) {
      //cerr << i << ' ';
      //cerr << t[i].off << ' ';
      lazy[i] = true;
      propagate(i, l, r);
      //cerr << t[i].on << ' ';
      return;
    }
    int mid = (l+r)/2;
    update(2*i, l, mid, qL, qR);
    update(2*i+1, mid+1, r, qL, qR);
    updt(i);
    //cerr << t[i].on << ' ';
  }
};


int m, n;
segTree seg;
void init(int N, int M, vector<int> P, vector<int> A) {
  m = M; n = N;
  seg.init(M);
  seg.build(1, 0, M-1, A);
}

int count_ways(int L, int R) {
  seg.update(1, 0, m-1, L-n, R-n);
  return(seg.t[1].on);
}

• 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