oj.uz

Submission #825628

# Submission time Handle Problem Language Result Execution time Memory
825628 2023-08-15T06:39:06 Z ttamx Digital Circuit (IOI22_circuit) C++17
18 / 100
 672 ms 3132 KB 
#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.0 / 2.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 1712 KB Output is correct
2 Correct 421 ms 3104 KB Output is correct
3 Correct 663 ms 3132 KB Output is correct
4 Correct 530 ms 3104 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 1712 KB Output is correct
2 Correct 421 ms 3104 KB Output is correct
3 Correct 663 ms 3132 KB Output is correct
4 Correct 530 ms 3104 KB Output is correct
5 Correct 551 ms 1708 KB Output is correct
6 Correct 658 ms 3112 KB Output is correct
7 Correct 654 ms 3024 KB Output is correct
8 Correct 654 ms 3112 KB Output is correct
9 Correct 306 ms 336 KB Output is correct
10 Correct 634 ms 464 KB Output is correct
11 Correct 672 ms 464 KB Output is correct
12 Correct 606 ms 464 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 0 ms 208 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '475885760'
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 1 ms 252 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 0 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 0 ms 336 KB Output is correct
14 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '475885760'
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 1 ms 252 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 0 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 0 ms 336 KB Output is correct
14 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '475885760'
15 Halted 0 ms 0 KB -