oj.uz

Submission #955523

# Submission time Handle Problem Language Result Execution time Memory
955523 2024-03-30T19:33:58 Z StefanSebez Digital Circuit (IOI22_circuit) C++17
18 / 100
 758 ms 22648 KB 
#include "circuit.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int N=1e5+500;
const ll mod=1000002022;
ll Puta(ll a,ll b){a%=mod,b%=mod;ll x=a*b;x%=mod;return x;}
ll Plus(ll a,ll b){a%=mod,b%=mod;ll x=a+b;x%=mod;while(x<0) x+=mod;return x;}
vector<int>E[2*N+500];
int a[N+500],n,m,P[2*N+500];
ll res[N+500],dp[2*N+500][2],F[2*N+500],F1[2*N+500];
bool stepen2;
void DFSsetup(int u){
	if(E[u].empty()) return;
	F[u]=E[u].size();
	for(auto i:E[u]){
		DFSsetup(i);
		F[u]=Puta(F[u],F[i]);
	}
	for(auto i:E[u]){
		F1[i]=1;
		for(auto j:E[u]){
			if(j!=i) F1[i]=Puta(F1[i],F[j]);
		}
	}
}
void DFS(int u){
	if(E[u].empty()) return;
	for(auto i:E[u]) DFS(i);
	dp[u][1]=0;
	for(auto i:E[u]) dp[u][1]=Plus(dp[u][1],Puta(dp[i][1],F1[i]));
	//printf("%i: %lld %lld\n",u,dp[u][1],F[u]);
	/*int mask=0;
	while(mask< (1<<(E[u].size()))){
		ll temp1=1,sum=0;
		for(int i=0,temp=mask;i<E[u].size();i++,temp/=2){
			temp1=Puta(temp1,dp[E[u][i]][temp%2]);sum+=temp%2;
		}
		if(mask!=0) dp[u][1]=Plus(dp[u][1],Puta(sum,temp1));
		dp[u][0]=Plus(dp[u][0],Puta(E[u].size()-sum,temp1));
		mask++;
	}*/
	//dp[u][0]=F[u]-dp[u][1];
}
void Update1(int v){
	dp[v][1]=1-dp[v][1];
	dp[v][0]=1-dp[v][0];
	int u=P[v];
	while(u!=-1){
		dp[u][1]=0;
		for(auto i:E[u]) dp[u][1]=Plus(dp[u][1],Puta(dp[i][1],F1[i]));
		/*dp[u][1]=dp[u][0]=0;
		int mask=0;
		while(mask< (1<<(E[u].size()))){
			ll temp1=1,sum=0;
			for(int i=0,temp=mask;i<E[u].size();i++,temp/=2){
				temp1=Puta(temp1,dp[E[u][i]][temp%2]);sum+=temp%2;
			}
			if(mask!=0) dp[u][1]=Plus(dp[u][1],Puta(sum,temp1));
			dp[u][0]=Plus(dp[u][0],Puta(E[u].size()-sum,temp1));
			mask++;
		}*/
		u=P[u];
	}
}
int nc,root,lc[2*N],rc[2*N],sum[2*N],lazy[2*N];
void update(int &c,int ss,int se,int qval){
	if(!c) c=++nc;
	if(qval==0) return;
	sum[c]=se-ss+1-sum[c];
	lazy[c]++;lazy[c]%=2;
}
void push(int &c,int ss,int se){
	int mid=(ss+se)/2;
	update(lc[c],ss,mid,lazy[c]);
	update(rc[c],mid+1,se,lazy[c]);
	lazy[c]=0;
}
void Update(int &c,int ss,int se,int qs,int qe){
	if(!c) c=++nc;
	if(qs<=ss && se<=qe){
		update(c,ss,se,1);
		//printf("%i %i %i: %i\n",c,ss,se,sum[c]);
		return;
	}
	if(qe<ss || se<qs) return;
	int mid=(ss+se)/2;
	push(c,ss,se);
	Update(lc[c],ss,mid,qs,qe);Update(rc[c],mid+1,se,qs,qe);
	sum[c]=sum[lc[c]]+sum[rc[c]];
	//printf("%i %i %i: %i\n",c,ss,se,sum[c]);
}
int Get(int c,int ss,int se,int qs,int qe){
	//printf("%i %i %i: %i\n",c,ss,se,sum[c]);
	if(qs<=ss && se<=qe) return sum[c];
	if(qe<ss || se<qs) return 0;
	int mid=(ss+se)/2;
	push(c,ss,se);
	return Get(lc[c],ss,mid,qs,qe)+Get(rc[c],mid+1,se,qs,qe);
}

int tajm,in[2*N],out[2*N],LL[2*N],RR[2*N];
void DFSsetup2(int u){
	in[u]=++tajm;
	for(auto i:E[u]) DFSsetup2(i);
	out[u]=tajm;
}
int lazy2[2*N];
void update2(int u,int qval){
	if(qval==0) return;
	dp[u][1]=Plus(F[u],-dp[u][1]);
	lazy2[u]++;lazy2[u]%=2;
}
void push2(int u){
	for(auto i:E[u]) update2(i,lazy2[u]);
	lazy2[u]=0;
}
void Update2(int u,int qs,int qe){
	if(qs<=LL[u] && RR[u]<=qe) {update2(u,1);return;}
	if(qe<LL[u] || RR[u]<qs) return;
	push2(u);
	for(auto i:E[u]) Update2(i,qs,qe);
	dp[u][1]=0;
	for(auto i:E[u]) dp[u][1]=Plus(dp[u][1],Puta(dp[i][1],F1[i]));
	//printf("%i %i %i: %i\n",u,LL[u],RR[u],dp[u][1]);
}

void init(int N1, int M1, std::vector<int> P1, std::vector<int> A) {
	n=N1,m=M1;
	for(int i=0;i<P1.size();i++) P[i]=P1[i];
	for(int i=0;i<P1.size();i++){
		E[P[i]].pb(i);
	}
	for(int i=0;i<m;i++){
		dp[n+i][1]=A[i],dp[n+i][0]=1-A[i];
		a[i]=A[i];
		F[n+i]=1;
	}
	DFSsetup2(0);
	for(int i=0;i<n+m;i++){
		int lb=lower_bound(in+n,in+n+m-1,in[i])-in,ub=lower_bound(out+n,out+n+m-1,out[i])-out;
		LL[i]=lb,RR[i]=ub;
		//printf("%i: %i %i %i %i\n",i,in[i],out[i],LL[i],RR[i]);
	}
	DFSsetup(0);
	DFS(0);
	int temp=m,ct=0;while(temp>0) ct+=temp%2,temp/=2;if(ct==1) stepen2=true;
	if(!stepen2 || n<=5000) return;
	for(int i=n;i<n+m;i++) dp[i][1]=0;
	DFS(0);
	res[0]=dp[0][1];
	for(int i=0;i<m;i++){
		Update1(n+i);
		res[i+1]=dp[0][1];
	}
	for(int i=0;i<m;i++) if(a[i]==1) Update(root,0,m-1,i,i);
}

int count_ways(int L, int R) {
	if(n<=5000){
		Update2(0,L,R);
		return dp[0][1];
	}
	if(stepen2){
		Update(root,0,m-1,L-n,R-n);
		return res[Get(root,0,m-1,0,m-1)];
	}
	for(int i=L;i<=R;i++) Update1(i);
	return dp[0][1];
}

Compilation message

circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:134:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |  for(int i=0;i<P1.size();i++) P[i]=P1[i];
      |              ~^~~~~~~~~~
circuit.cpp:135:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |  for(int i=0;i<P1.size();i++){
      |              ~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14168 KB Output is correct
2 Correct 4 ms 14168 KB Output is correct
3 Correct 10 ms 14424 KB Output is correct
4 Correct 10 ms 14168 KB Output is correct
5 Correct 10 ms 14168 KB Output is correct
6 Correct 10 ms 14168 KB Output is correct
7 Correct 10 ms 14168 KB Output is correct
8 Correct 10 ms 14168 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 19484 KB Output is correct
2 Correct 663 ms 22440 KB Output is correct
3 Correct 667 ms 22424 KB Output is correct
4 Correct 644 ms 22480 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 19484 KB Output is correct
2 Correct 663 ms 22440 KB Output is correct
3 Correct 667 ms 22424 KB Output is correct
4 Correct 644 ms 22480 KB Output is correct
5 Correct 554 ms 19744 KB Output is correct
6 Correct 758 ms 22648 KB Output is correct
7 Correct 739 ms 22388 KB Output is correct
8 Correct 659 ms 22132 KB Output is correct
9 Correct 302 ms 14168 KB Output is correct
10 Correct 712 ms 14424 KB Output is correct
11 Correct 684 ms 14424 KB Output is correct
12 Correct 631 ms 14424 KB Output is correct

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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