oj.uz

Submission #1044612

# Submission time Handle Problem Language Result Execution time Memory
1044612 2024-08-05T11:38:16 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 129 ms 13288 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], last[maxN];

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') {
			last[i] = 0;
			seg.modify(i, 0);
		} else {
			last[i] = INF;
			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') {
				ans[i] += timer - last[i];
				last[i] = INF;
				seg.modify(i, INF);
				S[i] = '0';
			} else {
				last[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 = ans[A];
				debug(get);
				if(last[A] != INF) {
					debug(timer, last[A]);
					get += timer - last[A];
				}
				std::cout << get << '\n';
			} else 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];
			}
			for(int i = 0; i < N; ++i) {
				std::cerr << ans[i] << " \n"[i == N - 1];
			}
			for(int i = 0; i < N; ++i) {
				std::cerr << last[i] << " \n"[i == N - 1];
			}
			debug();
		#endif
	}

	return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1364 KB Output is correct
2 Correct 48 ms 4692 KB Output is correct
3 Correct 56 ms 5328 KB Output is correct
4 Correct 89 ms 11236 KB Output is correct
5 Correct 93 ms 11748 KB Output is correct
6 Correct 86 ms 10984 KB Output is correct
7 Correct 109 ms 11752 KB Output is correct
8 Correct 106 ms 13288 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 73 ms 5360 KB Output is correct
6 Correct 88 ms 5604 KB Output is correct
7 Correct 104 ms 5604 KB Output is correct
8 Correct 120 ms 7328 KB Output is correct
9 Correct 52 ms 1108 KB Output is correct
10 Correct 45 ms 1116 KB Output is correct
11 Correct 47 ms 1344 KB Output is correct
12 Correct 117 ms 5964 KB Output is correct
13 Correct 129 ms 7396 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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