제출 #636745

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
636745		sentheta	디지털 회로 (IOI22_circuit)	C++17	100 / 100	1172 ms	25276 KiB

circuit

#include "circuit.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

#define rand() (uniform_int_distribution<int>(0,1<<30)(rng))
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

const Int MOD = 1e9+2022;



const int N = 1e5+5;

int n, m;
V<int> p;


#define mid (tl+tr)/2
#define lc v+1
#define rc v+2*(mid-tl+1)

struct Multree{
	Int st[4*N];
	Multree(){
		rep(i,0,4*N) st[i] = 1;
	}
	void upd(int l,int r,int x,int v=0,int tl=0,int tr=n+m-1){
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r){
			(st[v] *= x )%=MOD; return;
		}
		upd(l,r,x, lc,tl,mid);
		upd(l,r,x, rc,mid+1,tr);
	}
	Int qry(int i,int v=0,int tl=0,int tr=n+m-1){
		if(tl==tr) return st[v];
		if(i<=mid) return st[v] *qry(i, lc,tl,mid)%MOD ;
		else return st[v] *qry(i, rc,mid+1,tr)%MOD;
	}
} multree;


struct Fliptree{
	int st[2*N][2];
	bool lz[2*N];
	void assign(int i,int x,int v=0,int tl=0,int tr=m-1){
		if(tl==tr){
			st[v][0] = x; return;
		}
		if(i<=mid) assign(i,x, lc,tl,mid);
		else assign(i,x, rc,mid+1,tr);
		rep(i,0,2)
			(st[v][i] = st[lc][i] + st[rc][i] )%=MOD;
	}
	void flip(int l,int r,int v=0,int tl=0,int tr=m-1){
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r){
			swap(st[v][0], st[v][1]);
			lz[v] ^= 1; return;
		}
		if(lz[v]){
			flip(tl,tr, lc,tl,mid);
			flip(tl,tr, rc,mid+1,tr);
			lz[v] = 0;
		}
		flip(l,r, lc,tl,mid);
		flip(l,r, rc,mid+1,tr);
		rep(i,0,2)
			(st[v][i] = st[lc][i] + st[rc][i] )%=MOD;
	}
	int qry(){
		return st[0][1];
	}
} fliptree;


V<int> adj[2*N];
int in[2*N], out[2*N], timer=0;
Int dp[2*N];
void dfs(int x=0){
	in[x] = timer++;

	if(adj[x].size()==0) dp[x] = 1;
	else dp[x] = adj[x].size();

	for(int y : adj[x]){
		dfs(y);
		(dp[x] *= dp[y] )%=MOD;
	}
	out[x] = timer-1;
}


void init(int _n,int _m,V<int> _p,V<int> a){
	n = _n; m = _m; p.swap(_p);

	rep(i,1,n+m){
		adj[p[i]].push_back(i);
	}
	dfs();

	rep(i,1,n+m){
		// dbg(i); dbg(dp[i]);
		// dbg(in[i]); dbg(out[i]);
		if(in[p[i]]+1 <= in[i]-1){
			// cout << in[p[i]]+1 _ in[i]-1 << nl;
			multree.upd(in[p[i]]+1,in[i]-1, dp[i]);
		}
		if(out[i]+1 <= out[p[i]]){
			// cout << out[i]+1 _ out[p[i]] << nl;
			multree.upd(out[i]+1, out[p[i]], dp[i]);
		}
		// cout << nl;
	}

	rep(i,0,m){
		// dbg(in[n+i]);
		// dbg(multree.qry(in[n+i]));
		fliptree.assign(i, multree.qry(in[n+i]));
		if(a[i]){
			fliptree.flip(i,i);
		}
	}

	// dbg(fliptree.qry());
}

int count_ways(int l,int r){
	// return -1;
	l -= n; r -= n;
	fliptree.flip(l, r);
	return fliptree.qry();
}

• 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