Submission #1187788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187788		ByeWorld	Digital Circuit (IOI22_circuit)	C++20	52 / 100	356 ms	39972 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf ((id<<1))
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 3e5+10;
const ll MOD = 1e9+2022;
ll sum(ll a, ll b){ return (a+b)%MOD;}
ll sub(ll a, ll b){ return (a+MOD-b)%MOD;}
void chsum(ll &a, ll b){ a = (a+b)%MOD;}
ll mul(ll a, ll b){ return (a*b)%MOD; }
void chmul(ll &a, ll b){ a = (a*b)%MOD;}
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }

int n, m, par[MAXN], a[MAXN];
ll dp[MAXN][3], up[MAXN], val[MAXN], two[MAXN];
vector<int> adj[MAXN];

void dfs(int nw, int par){
	if(adj[nw].empty()){
		up[nw] = up[par]; 
		val[nw] = two[n-up[nw]];
		return;
	}
	up[nw] = up[par]+1;
	for(auto nx : adj[nw]) dfs(nx, nw);
}

struct node {
	ll zer = 0, one = 0;
} NOL;
struct seg {
	node st[4*MAXN]; int laz[4*MAXN];
	node mrg(node a, node b){
		node ret;
		ret.one = sum(a.one, b.one);
		ret.zer = sum(a.zer, b.zer);
		return ret;
	}
	void push(int id, int v){
		swap(st[id].one, st[id].zer);
		laz[id] ^= v;
	}
	void bnc(int id){
		if(laz[id]==0) return;
		push(lf,laz[id]); push(rg,laz[id]);
		laz[id] = 0;
	}
	void bd(int id, int l, int r){
		if(l==r){
			if(a[l+n] == 1){
				st[id].one = val[l+n];
			} else {
				st[id].zer = val[l+n];
			}
			return;
		}
		bd(lf,l,md); bd(rg,md+1,r);
		st[id] = mrg(st[lf], st[rg]);
	}
	node upd(int id, int l, int r, int x, int y){
		if(x<=l && r<=y){
			push(id, 1);
			return st[id];
		}
		if(r<x || y<l) return st[id];
		bnc(id);
		return st[id] = mrg(upd(lf,l,md,x,y), upd(rg,md+1,r,x,y));
	}
} A;
void init(int N, int M, std::vector<int> P, std::vector<int> AA) {
	n = N; m = M;
	two[0] = 1;
	for(int i=1; i<=n+m; i++) two[i] = mul(two[i-1], 2);

	for(int i=1; i<=n+m; i++){
		par[i] = P[i-1]+1;
		adj[par[i]].pb(i);
	}
	for(int i=1; i<=m; i++){
		a[i+n] = AA[i-1];
	}
	dfs(1, 0);
	A.bd(1,1,m);
}

int count_ways(int L, int R) {
	int l = L+1, r = R+1;
	A.upd(1,1,m,l-n,r-n);
	
	// for(int i=1; i<=13; i++){
	// 	cout << i << ' ' <<dp[i][0] << ' ' << dp[i][1] << " xx\n";
	// }
	return (int)A.st[1].one;
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 0 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11