oj.uz

Submission #736430

# Submission time Handle Problem Language Result Execution time Memory
736430 2023-05-05T15:57:04 Z jk410 Digital Circuit (IOI22_circuit) C++17
0 / 100
 693 ms 2020 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000002022;
ll pow2[100000];
struct node {
	int sz;
	ll val;
};
node operator+(const node& a, const node& b) {
	node ret;
	ret.sz = a.sz + b.sz + 1;
	ret.val = a.val * b.val % MOD;
	ret.val = (ret.val + (pow2[a.sz] - a.val + MOD) % MOD * b.val % MOD) % MOD;
	ret.val = (ret.val + (pow2[b.sz] - b.val + MOD) % MOD * a.val % MOD) % MOD;
	return ret;
}

int N,M;

bool lazy[200000];
node tree[200000];

void propagate(int l, int r, int n) {
	if (!lazy[n])
		return;
	if (l == r)
		tree[n].val ^= 1;
	else {
		int m = (l + r) >> 1;
		lazy[n << 1] = !lazy[n << 1];
		lazy[n << 1 | 1] = !lazy[n << 1 | 1];
	}
	lazy[n] = false;
}

node update(int lx, int rx, int l, int r, int n) {
	propagate(l, r, n);
	if (r < lx || rx < l)
		return tree[n];
	if (lx <= l && r <= rx) {
		lazy[n] = !lazy[n];
		propagate(l, r, n);
		return tree[n];
	}
	int m = (l + r) >> 1;
	return tree[n] = update(lx, rx, l, m, n << 1) + update(lx, rx, m + 1, r, n << 1 | 1);
}

void init(int _n, int m, vector<int> _p, vector<int> a) {
	N = _n;
	pow2[0] = 1;
	for (int i = 1; i <= N; i++)
		pow2[i] = pow2[i - 1] * 2 % MOD;
	for (int i = 0; i < M; i++) {
		if (a[i])
			update(i, i, 0, N, 1);
	}
}

int count_ways(int l, int r) {
	update(l - N, r - N, 0, N, 1);
	return tree[1].val;
}

Compilation message

circuit.cpp: In function 'void propagate(int, int, int)':
circuit.cpp:31:7: warning: unused variable 'm' [-Wunused-variable]
   31 |   int m = (l + r) >> 1;
      |       ^

Subtask #1
0 / 2.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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