Submission #825628

#	Time	Username	Problem	Language	Result	Execution time	Memory
825628		ttamx	Digital Circuit (IOI22_circuit)	C++17	18 / 100	672 ms	3132 KiB

circuit

#include "circuit.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e5+5;
const int K=1<<18;
const ll mod=1e9+2022;

int n,m;
int a[N];
ll pw[N];
ll mul;

struct segtree{
	int t[K];
	bool lz[K];
	void pushlz(int l,int r,int i){
		if(!lz[i])return;
		t[i]=r-l+1-t[i];
		if(l<r){
			lz[i*2]^=true;
			lz[i*2+1]^=true;
		}
		lz[i]=false;
	}
	void build(int l,int r,int i){
		if(l==r)return void(t[i]=a[l]);
		int m=(l+r)/2;
		build(l,m,i*2);
		build(m+1,r,i*2+1);
		t[i]=t[i*2]+t[i*2+1];
	}
	void build(){
		build(1,m,1);
	}
	void update(int l,int r,int i,int x,int y){
		pushlz(l,r,i);
		if(y<l||r<x)return;
		if(x<=l&&r<=y)return lz[i]=true,pushlz(l,r,i),void();
		int m=(l+r)/2;
		update(l,m,i*2,x,y);
		update(m+1,r,i*2+1,x,y);
		t[i]=t[i*2]+t[i*2+1];
	}
	void update(int x,int y){
		update(1,m,1,x,y);
	}
}s;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
	n=N,m=M;
	pw[0]=1;
	for(int i=1;i<=n;i++)pw[i]=pw[i-1]*2%mod;
	for(int i=1;i<=m;i++)a[i]=A[i-1];
	s.build();
	int cur=1;
	mul=1;
	while(cur<n){
		mul*=pw[cur];
		mul%=mod;
		cur=cur*2+1;
	}
}

int count_ways(int L, int R) {
	L-=n-1;
	R-=n-1;
	s.update(L,R);
	return (mul*s.t[1])%mod;
}

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