oj.uz

Submission #1058128

# Submission time Handle Problem Language Result Execution time Memory
1058128 2024-08-14T08:37:58 Z tolbi Digital Circuit (IOI22_circuit) C++17
16 / 100
 596 ms 10840 KB 
#include "circuit.h"

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

constexpr int MAXN = 500000;
constexpr int MOD = 1e9+2022;
void prep(array<int,2> &a, array<int,2> &b, array<int,2> &c){
	int sif = (1ll*b[0]*c[0])%MOD;
	int bir = ((1ll*b[0]*c[1])%MOD)+((1ll*b[1]*c[0])%MOD);
	if (bir>=MOD) bir-=MOD;
	int iki = (1ll*b[1]*c[1])%MOD;
	a[0]=(2ll*sif+bir)%MOD;
	a[1]=(2ll*iki+bir)%MOD;
}
struct SegTree{
	int tag[MAXN];
	array<int,2> ans[MAXN], rev[MAXN];
	int sz;
	void upd(int node){
		prep(ans[node],ans[node*2+1],ans[node*2+2]);
		prep(rev[node],rev[node*2+1],rev[node*2+2]);
	}
	void dallan(int node){
		if (tag[node]){
			swap(ans[node],rev[node]);
			if (node*2+1<sz){
				tag[node*2+1]^=1;
				tag[node*2+2]^=1;
			}
			tag[node]=0;
		}
	}
	SegTree(vector<int> arr):sz(arr.size()*2-1){
		fill(tag,tag+sz,0);
		for (int i = 0; i < arr.size(); i++){
			ans[i+sz/2][arr[i]]=1;
			ans[i+sz/2][arr[i]^1]=0;
			rev[i+sz/2]=ans[i+sz/2];
			swap(rev[i+sz/2][0],rev[i+sz/2][1]);
		}
		for (int i = sz/2-1; i >= 0; i--){
			upd(i);
		}
	}
	void update(int tl, int tr, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = sz/2;
		dallan(node);
		if (l>=tl && r<=tr){
			return tag[node]=1,dallan(node);
		}
		if (l>tr || r<tl) return;
		int mid = l+(r-l)/2;
		if (tl<=mid) update(tl,tr,l,mid,node*2+1);
		else dallan(node*2+1);
		if (mid<tr) update(tl,tr,mid+1,r,node*2+2);
		else dallan(node*2+2);
		upd(node);
	}
} *segtree=nullptr;
int n;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
	n=N;
	segtree=new SegTree(A);
}

int count_ways(int L, int R) {
	L-=n,R-=n;
	segtree->update(L,R);
	return (segtree->ans)[0][1];
}

Compilation message

circuit.cpp: In constructor 'SegTree::SegTree(std::vector<int>)':
circuit.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for (int i = 0; i < arr.size(); i++){
      |                   ~~^~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 0 ms 4440 KB Output is correct
3 Incorrect 0 ms 4440 KB 1st lines differ - on the 1st token, expected: '509', found: '445971608'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 0 ms 4440 KB Output is correct
3 Incorrect 0 ms 4440 KB 1st lines differ - on the 1st token, expected: '509', found: '445971608'
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 7768 KB Output is correct
2 Correct 594 ms 6744 KB Output is correct
3 Correct 596 ms 10584 KB Output is correct
4 Correct 533 ms 10328 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 7768 KB Output is correct
2 Correct 594 ms 6744 KB Output is correct
3 Correct 596 ms 10584 KB Output is correct
4 Correct 533 ms 10328 KB Output is correct
5 Correct 450 ms 5544 KB Output is correct
6 Correct 589 ms 10840 KB Output is correct
7 Correct 586 ms 6764 KB Output is correct
8 Correct 539 ms 8792 KB Output is correct
9 Correct 263 ms 4440 KB Output is correct
10 Correct 500 ms 4696 KB Output is correct
11 Correct 471 ms 4696 KB Output is correct
12 Correct 506 ms 4696 KB Output is correct

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 0 ms 4440 KB Output is correct
3 Incorrect 0 ms 4440 KB 1st lines differ - on the 1st token, expected: '509', found: '445971608'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 0 ms 4440 KB Output is correct
3 Incorrect 0 ms 4440 KB 1st lines differ - on the 1st token, expected: '509', found: '445971608'
4 Halted 0 ms 0 KB -