oj.uz

Submission #1044601

# Submission time Handle Problem Language Result Execution time Memory
1044601 2024-08-05T11:30:36 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 139 ms 6372 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;
constexpr int maxN = int(3E5 + 5);

int ans[maxN];

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

	std::fill(ans, ans + maxN, INF);

	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') {
			ans[i] = 0;
			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 {
				ans[i] = timer;
				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(A + 1 == B) {
				get = std::min(get, ans[A]);
			}
			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 1628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 2020 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 1624 KB Output is correct
2 Correct 2 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 101 ms 4332 KB Output is correct
6 Correct 98 ms 4444 KB Output is correct
7 Correct 110 ms 4580 KB Output is correct
8 Correct 122 ms 6332 KB Output is correct
9 Correct 67 ms 2388 KB Output is correct
10 Correct 74 ms 2384 KB Output is correct
11 Correct 51 ms 2388 KB Output is correct
12 Correct 139 ms 4836 KB Output is correct
13 Correct 118 ms 6372 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Incorrect 1 ms 1628 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 1628 KB Output isn't correct
2 Halted 0 ms 0 KB -