Submission #1215063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215063		dosts	Digital Circuit (IOI22_circuit)	C++17	0 / 100	184 ms	4124 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+2022, LIM = 1e6+1, inf = 2e9;

int add(int x,int y) {
    if ((x + y) >= MOD) return x + y - MOD;
    return x + y;
}

int mult(int x,int y) {
    return (1LL * x * y) % MOD;
}

int expo(int x,int y) {
  if (!y) return 1;
  int e = expo(x,y/2);
  e = mult(e,e);
  if (y&1) e= mult(e,x);
  return e;
}

//range toggle mass sum
struct ST {
  vector<pii> t;
  vi lazy;

  void build(int node,int l,int r) {
    if (l > r) return;
    lazy[node] = 0;
    t[node] = {0,r-l+1};
    if (l == r) return;
    int m = (l+r) >> 1;
    build(2*node,l,m),build(2*node+1,m+1,r);
  }
  ST(){}
  ST(int nn) {
    t.resize(4*nn+1);
    lazy.resize(4*nn+1);
    build(1,1,nn);
  }
  void push(int node,bool leaf) {
    if (!lazy[node]) return;
    t[node].ff = t[node].ss-t[node].ff;
    if (!leaf) {
      lazy[2*node]^=1;
      lazy[2*node+1]^=1;
    }
    lazy[node] = 0;
  }

  void update(int node,int l,int r,int L,int R) {
    push(node,l==r);
    if (l > R || r < L) return;
    if (l >=L && r <= R) {
      lazy[node]^=1;
      push(node,l==r);
      return;
    }
    int m = (l+r) >> 1;
    update(2*node,l,m,L,R),update(2*node+1,m+1,r,L,R);
    t[node].ff = t[2*node].ff+t[2*node+1].ff;
  }

  int query(int node,int l,int r,int L,int R) {
    push(node,l==r);
    if (l > R || r < L) return 0;
    if (l >= L && r <= R) return t[node].ff;
    int m = (l+r) >> 1;
    return query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R);
  }
} st;
int mm;
void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
  st = ST(M);
  mm = M;
  for (int i = 0;i<M;i++) if (A[i]) st.update(1,1,M,i+1,i+1);
}

int32_t count_ways(int32_t L, int32_t R) {
  st.update(1,1,mm,L+1,R+1);
  return add(expo(2,st.query(1,1,mm,1,mm)),MOD-1);
}

• 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