Submission #1061226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061226		epicci23	Digital Circuit (IOI22_circuit)	C++17	100 / 100	769 ms	42200 KiB

circuit

#include "bits/stdc++.h"
#include "circuit.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int64_t) a.size()
using namespace std;

const int64_t MOD = 1000002022;

int64_t add(int64_t a,int64_t b){
  if(a+b>=MOD) return a+b-MOD;
  return a+b;
}

int64_t mult(int64_t a,int64_t b){
 if((a*b)>=MOD) return (a*b)%MOD;
 return a*b;
}

const int N = 2e5 + 5;
vector<int> v[N];
int64_t sub[N],n,m;
vector<int64_t> ans,col;

struct SegT{
  vector<array<int64_t,2>> v;
  vector<int> lazy;
  void init(int n){
  	lazy.resize(4*n+5,0);
    v.resize(4*n+5);
  }
  array<int64_t,2> merge(array<int64_t,2> a,array<int64_t,2> b){
  	array<int64_t,2> res;
  	res[0]=add(a[0],b[0]);
  	res[1]=add(a[1],b[1]);
  	return res;
  }
  void build(int rt,int l,int r){
  	if(l==r){
  	  v[rt][0]=mult(col[l],ans[l]);
  	  v[rt][1]=mult(1-col[l],ans[l]);
      //cout << n+l << ' ' <<  col[l] << ' ' << v[rt][0] << ' ' << v[rt][1] << '\n'; 
  	  return;
  	}
  	int m=(l+r)/2;
  	build(rt*2,l,m),build(rt*2+1,m+1,r);
  	v[rt]=merge(v[rt*2],v[rt*2+1]);
  }
  void push(int rt,int l,int r){
    if(!lazy[rt]) return;
    swap(v[rt][0],v[rt][1]);
    lazy[rt]=0;
    if(l==r) return;
    lazy[rt*2]^=1;
    lazy[rt*2+1]^=1;
  }
  void upd(int rt,int l,int r,int gl,int gr){
  	push(rt,l,r);
    if(r<gl || l>gr) return;
    if(l>=gl && r<=gr){
      lazy[rt]^=1;
      push(rt,l,r);
      return;
    }
    int m=(l+r)/2;
    upd(rt*2,l,m,gl,gr),upd(rt*2+1,m+1,r,gl,gr);
    v[rt]=merge(v[rt*2],v[rt*2+1]);
  }
};

SegT seg;

void dfs(int c){
  int64_t res=1;
  for(int x:v[c]){
   dfs(x);
   res=mult(res,sub[x]);
  }
  if(sz(v[c])>0) res=mult(res,sz(v[c]));
  sub[c]=res;
}

void dfs2(int c,int64_t val){
  if(sz(v[c])==0){
    ans[c-n]=val;
    return;
  }
  vector<int64_t> pre(sz(v[c])),suf(sz(v[c]));
  int64_t cur=1;
  for(int i=0;i<sz(v[c]);i++){
    cur=mult(cur,sub[v[c][i]]);
    pre[i]=cur;
  }
  cur=1;
  for(int i=sz(v[c])-1;i>=0;i--){
  	cur=mult(cur,sub[v[c][i]]);
  	suf[i]=cur;
  }
  for(int i=0;i<sz(v[c]);i++)
  	dfs2(v[c][i],mult((i+1<sz(v[c])?suf[i+1]:1),mult(val,(i>0 ? pre[i-1] : 1))));
}

void init(int N, int M, vector<int> P, vector<int> A){
  n=N,m=M;
  ans.resize(m),col.resize(m);
  for(int i=1;i<n+m;i++) v[P[i]].push_back(i);
  for(int i=0;i<m;i++) col[i]=A[i];
  dfs(0),dfs2(0,1);
  seg.init(m);
  seg.build(1,0,m-1);
}

int count_ways(int L, int R){
  L-=n,R-=n;
  seg.upd(1,0,m-1,L,R);
  return (int32_t)seg.v[1][0];
}

/*void _(){
  cin >> n >> m;
  ans.resize(m),col.resize(m);
  for(int i=0;i<n+m;i++){
  	int a;cin >> a;
  	if(a>=0) v[a].push_back(i);
  }
  for(int i=0;i<m;i++) cin >> col[i];
  dfs(0),dfs2(0,1);
  SegT seg(m);
  seg.build(1,0,m-1);
  int q;cin >> q;
  while(q--){
  	int l,r;
  	cin >> l >> r;
    l-=n;r-=n;
  	seg.upd(1,0,m-1,l,r);
  	cout << seg.v[1][0] << '\n';
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

• 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