Submission #638256

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
638256	2022-09-05T06:24:45 Z	jamezzz	Digital Circuit (IOI22_circuit)	C++17	2 / 100	716 ms	4152 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));
}

Subtask #1
2.0 / 2.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	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	Memory	Grader output
1	Correct	208 KB	Output is correct
2	Incorrect	208 KB	1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
3	Halted	0 KB	-

Subtask #3
0 / 9.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	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	Incorrect	0 ms	208 KB	1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
11	Halted	0 ms	0 KB	-

Subtask #4
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	716 ms	4152 KB	1st lines differ - on the 1st token, expected: '431985922', found: '-747097920'
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	716 ms	4152 KB	1st lines differ - on the 1st token, expected: '431985922', found: '-747097920'
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	Verdict	Memory	Grader output
1	Correct	208 KB	Output is correct
2	Incorrect	208 KB	1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
3	Halted	0 KB	-

Subtask #7
0 / 28.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	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	Incorrect	0 ms	208 KB	1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
11	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	1 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	Incorrect	0 ms	208 KB	1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
11	Halted	0 ms	0 KB	-

Submission #638256

Compilation message