Submission #1136724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136724		Saul0906	Digital Circuit (IOI22_circuit)	C++20	0 / 100	211 ms	14460 KiB

circuit

#include "circuit.h"
#include <vector>
#include <bits/stdc++.h>
#define rep(a,b,c) for(ll a=b; a<c; a++)
#define repr(a,b,c) for(ll a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define ll long long
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define mid ((l+r)>>1)

using namespace std;
using vi = vector<int>;

const ll N=2e5+5, mod=1e9+2022;
vi adj[N];
ll v[N], sum[N];
bool sub5;

struct segtree{
	segtree *left, *right;
	ll l, r, s[2], c[2], dp[3], lazy=0;
	void calc(){
		rep(i,0,2) c[i]=left->c[i]+right->c[i];
		rep(i,0,2) s[i]=(left->s[i]+right->s[i])%mod;
		rep(i,0,3) dp[i]=(left->dp[i]*right->dp[i])%mod;
	}
	segtree(int x, int y): l(x), r(y){
		if(l==r){
			c[1]=v[l];
			c[0]=c[1]^1;
			s[0]=c[0]*sum[l];
			s[1]=c[1]*sum[l];
			dp[0]=c[0];
			dp[1]=c[1];
			dp[2]=0;
			return;
		}
		left = new segtree(l,mid);
		right= new segtree(mid+1,r);
		calc();
	}
	void prop(){
		if(!lazy) return;
		swap(c[0],c[1]);
		swap(s[0],s[1]);
		lazy=0;
		if(l==r){
			swap(dp[0],dp[1]);
			return;
		}
		left->lazy^=1;
		right->lazy^=1;
		swap(dp[0],dp[2]);
	}
	void update(int x, int y){
		prop();
		if(y<l || r<x) return;
		if(x<=l && r<=y){
			lazy=1;
			prop();
			return;
		}
		left->update(x,y);
		right->update(x,y);
		calc();
	}
} *st;

ll fpow(ll a, ll b){
	if(!b) return 1;
	if(b&1) return fpow(a,b-1)*a%mod;
	ll x=fpow(a,b/2);
	return x*x%mod;
}

void init(int n, int m, std::vector<int> p, std::vector<int> a) {
	rep(i,1,n+m) adj[p[i]].pb(i);
	rep(i,0,m) v[i+n]=a[i], sum[i+n]=fpow(2,n-p[i+n]-1);
	st = new segtree(n,n+m-1);
	sub5=true;
	rep(i,0,n) if(adj[i].size()!=2) sub5=false;
}

int count_ways(int l, int r) {
	st->update(l,r);
	assert(sub5);
	if(sub5) return st->s[1];
	return (st->dp[1]+st->dp[2]*2)%mod;
}

• 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