제출 #807554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
807554		Ozy	디지털 회로 (IOI22_circuit)	C++17	16 / 100	844 ms	4944 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 200000
#define mod 1000002022

struct x {
  lli unos;
  lli ceros;
  lli lazy;
};

x stree[MAX+2];
lli offset;

void push(lli pos){
  if (!stree[pos].lazy) return;

  swap(stree[pos].ceros, stree[pos].unos);
  if (pos < offset) {
    stree[pos*2].lazy ^= 1;
    stree[(pos*2)+1].lazy ^= 1;
  }

  stree[pos].lazy = 0;
  return;
}

x solve(x a, x b) {
  x res;

  res.ceros = a.ceros*b.ceros*2;
  res.unos = a.unos*b.unos*2;

  lli y = a.ceros*b.unos + b.ceros*a.unos;
  res.ceros += y;
  res.unos += y;
  
  res.ceros %= mod;
  res.unos %= mod;

  return res;
}

void update(lli pos, lli ini, lli fin, lli l, lli r) {
  push(pos);
  if(ini > r || fin < l) return;
  if (l <= ini && fin <= r) {
    stree[pos].lazy = 1;
    push(pos);
    return;
  }

  lli mitad = (ini+fin)/2;
  update(pos*2,ini,mitad,l,r);
  update(pos*2+1,mitad+1,fin,l,r);

  stree[pos] = solve(stree[pos*2], stree[pos*2+1]);
  return;
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {

  offset = 1;
  while (offset < M) offset *= 2;

  rep(i,offset,offset+M-1) {
    if  (A[i-offset] == 1) stree[i] = {1,0};
    else stree[i] = {0,1}; 
  }
  repa(pos,offset-1,1) stree[pos] = solve(stree[pos*2], stree[pos*2+1]);
}

int count_ways(int L, int R) {
  L -= (offset - 2);
  R -= (offset - 2);
  update(1,1,offset,L,R);

  return stree[1].unos;
}

• 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