oj.uz

Submission #1044607

# Submission time Handle Problem Language Result Execution time Memory
1044607 2024-08-05T11:31:25 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 142 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 {
				if(ans[i] == INF) {
					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 51 ms 2456 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 1 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 73 ms 4336 KB Output is correct
6 Correct 88 ms 4332 KB Output is correct
7 Correct 103 ms 4580 KB Output is correct
8 Correct 142 ms 6372 KB Output is correct
9 Correct 42 ms 2384 KB Output is correct
10 Correct 45 ms 2340 KB Output is correct
11 Correct 46 ms 2500 KB Output is correct
12 Correct 117 ms 4748 KB Output is correct
13 Correct 136 ms 6196 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 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 -