Submission #638257

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
638257	2022-09-05T06:25:18 Z	jamezzz	Digital Circuit (IOI22_circuit)	C++17	18 / 100	1044 ms	8108 KB

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.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	296 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Incorrect	1 ms	336 KB	1st lines differ - on the 1st token, expected: '706880838', found: '422083442'
7	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	0 ms	208 KB	Output is correct
10	Correct	1 ms	208 KB	Output is correct
11	Correct	1 ms	296 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Incorrect	1 ms	336 KB	1st lines differ - on the 1st token, expected: '706880838', found: '422083442'
15	Halted	0 ms	0 KB	-

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	640 ms	4148 KB	Output is correct
2	Correct	771 ms	7960 KB	Output is correct
3	Correct	925 ms	8108 KB	Output is correct
4	Correct	771 ms	7972 KB	Output is correct

Subtask #5
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	640 ms	4148 KB	Output is correct
2	Correct	771 ms	7960 KB	Output is correct
3	Correct	925 ms	8108 KB	Output is correct
4	Correct	771 ms	7972 KB	Output is correct
5	Correct	644 ms	4132 KB	Output is correct
6	Correct	1020 ms	8000 KB	Output is correct
7	Correct	1044 ms	7960 KB	Output is correct
8	Correct	741 ms	7996 KB	Output is correct
9	Correct	553 ms	464 KB	Output is correct
10	Correct	834 ms	720 KB	Output is correct
11	Correct	981 ms	720 KB	Output is correct
12	Correct	869 ms	720 KB	Output is correct

Subtask #6
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	296 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Incorrect	1 ms	336 KB	1st lines differ - on the 1st token, expected: '706880838', found: '422083442'
7	Halted	0 ms	0 KB	-

Subtask #7
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	0 ms	208 KB	Output is correct
10	Correct	1 ms	208 KB	Output is correct
11	Correct	1 ms	296 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Incorrect	1 ms	336 KB	1st lines differ - on the 1st token, expected: '706880838', found: '422083442'
15	Halted	0 ms	0 KB	-

Subtask #8
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	0 ms	208 KB	Output is correct
10	Correct	1 ms	208 KB	Output is correct
11	Correct	1 ms	296 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Incorrect	1 ms	336 KB	1st lines differ - on the 1st token, expected: '706880838', found: '422083442'
15	Halted	0 ms	0 KB	-

Submission #638257

Compilation message