oj.uz

Submission #1044589

# Submission time Handle Problem Language Result Execution time Memory
1044589 2024-08-05T11:23:02 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 134 ms 10980 KB 
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
	#include "debug.h"
#else 
	#define debug(...) void(23)
#endif

#define def int mid = (l + r) >> 1, rv = v + ((mid - l + 1) << 1)
struct segtree {
	int n;
	std::vector<int> tree;
	segtree(int _n) : n(_n), tree(n << 1) {}

	void modify(int v, int l, int r, int p, int x) {
		if(l == r) {
			tree[v] = x;
			return;
		}
		def;
		if(p <= mid) {
			modify(v + 1, l, mid, p, x);
		} else {
			modify(rv, mid + 1, r, p, x);
		}
		tree[v] = std::max(tree[v + 1], tree[rv]);
	}
	void modify(int p, int x) {
		assert(0 <= p && p < n);
		modify(0, 0, n - 1, p, x);
	}

	int query(int v, int l, int r, int ql, int qr) {
		if(ql <= l && r <= qr) {
			return tree[v];
		}
		def;
		if(qr <= mid) {
			return query(v + 1, l, mid, ql, qr);
		} else if(mid + 1 <= ql) {
			return query(rv, mid + 1, r, ql, qr);
		}
		return std::max(query(v + 1, l, mid, ql, qr), 
						query(rv, mid + 1, r, ql, qr));
	}
	int query(int l, int r) {
		assert(0 <= l && l <= r && r < n);
		return query(0, 0, n - 1, l, r);
	}
};

constexpr int INF = 1E9;

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int N, Q;
	std::cin >> N >> Q;
	std::string S;
	std::cin >> S;
	segtree seg(N);
	for(int i = 0; i < N; ++i) {
		if(S[i] == '1') {
			seg.modify(i, 0);
		} else {
			seg.modify(i, INF);
		}
	}

	for(int timer = 1; timer <= Q; ++timer) {
		std::string T;
		std::cin >> T;
		if(T[0] == 't') {
			int i;
			std::cin >> i;
			--i;
			if(S[i] == '1') {
				seg.modify(i, INF);
				S[i] = '0';
			} else {
				seg.modify(i, timer);
				S[i] = '1';
			}
		} else {
			int A, B;
			std::cin >> A >> B;
			--A, --B;
			int get = seg.query(A, B - 1);
			if(get == INF) {
				std::cout << 0 << '\n';
			} else {
				std::cout << timer - get << '\n';
			}
		}
		#ifdef DEBUG
			for(int i = 0; i < N; ++i) {
				std::cerr << seg.query(i, i) << " \n"[i == N - 1];
			}
		#endif
	}

	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 4044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 74 ms 7436 KB Output is correct
6 Correct 88 ms 8164 KB Output is correct
7 Correct 105 ms 8668 KB Output is correct
8 Correct 131 ms 10980 KB Output is correct
9 Correct 46 ms 3924 KB Output is correct
10 Correct 47 ms 4612 KB Output is correct
11 Correct 48 ms 4436 KB Output is correct
12 Correct 134 ms 9888 KB Output is correct
13 Correct 123 ms 10980 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -