Submission #1044614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044614		vjudge1	Street Lamps (APIO19_street_lamps)	C++17	60 / 100	121 ms	7404 KiB

street_lamps

#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;

	if(N <= 100 && Q <= 100) {
		std::vector<std::vector<int>> res(N, std::vector<int>(N));
		for(int timer = 0; timer < Q; ++timer) {
			for(int i = 0; i < N; ++i) {
				bool ok = true;
				for(int j = i; j < N && ok; ++j) {
					ok &= S[j] == '1';
					res[i][j] += ok;
				}
			}
			std::string T;
			std::cin >> T;
			if(T[0] == 't') {
				int i;
				std::cin >> i;
				--i;
				S[i] = (S[i] == '1' ? '0' : '1');
			} else {
				int A, B;
				std::cin >> A >> B;
				--A, --B;
				std::cout << res[A][B - 1] << '\n';
			}
		}

		return 0;
	}

	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: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20