Submission #638257

#	Time	Username	Problem	Language	Result	Execution time	Memory
638257		jamezzz	Digital Circuit (IOI22_circuit)	C++17	18 / 100	1044 ms	8108 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define maxn 100005
#define mod 1000002022

struct node{
	int s,e,m,v,lz;
	node *l,*r;
	node(int _s,int _e){
		s=_s;e=_e;m=(s+e)>>1;v=0;lz=0;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void ppo(){
		if(lz)v=(e-s+1)-v;
		if(s!=e){
			l->lz^=lz;
			r->lz^=lz;
		}
		lz=0;
	}
	void set(int x,int nv){
		if(s==x&&e==x){v=nv;return;}
		if(x<=m)l->set(x,nv);
		else r->set(x,nv);
		l->ppo(),r->ppo();
		v=l->v+r->v;
	}
	void flip(int x,int y){
		if(s==x&&e==y){lz^=1;return;}
		if(y<=m)l->flip(x,y);
		else if(x>m)r->flip(x,y);
		else l->flip(x,m),r->flip(m+1,y);
		l->ppo(),r->ppo();
		v=l->v+r->v;
	}
	int qry(int x,int y){
		ppo();
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return l->qry(x,m)+r->qry(m+1,y);
	}
}*root;

int n,m;
ll mult;

ll fpow(int a,int x){
	if(x==0)return 1;
	ll t=fpow(a,x/2);
	ll r=(t*t)%mod;
	if(x%2)r=(r*a)%mod;
	return r;
}

void init(int N,int M,vector<int> P,vector<int> A){
	n=N,m=M;
	int tmp=n+1,lg2=0;
	while(tmp!=1)++lg2,tmp/=2;
	mult=fpow(2,n-lg2);
	root=new node(0,M-1);
	for(int i=0;i<M;++i)root->set(i,A[i]);
}

int count_ways(int L,int R){
	root->flip(L-n,R-n);
	return (int)((mult*root->qry(0,m-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