oj.uz

Submission #475553

# Submission time Handle Problem Language Result Execution time Memory
475553 2021-09-22T22:13:44 Z thiago_bastos Street Lamps (APIO19_street_lamps) C++17
20 / 100
 229 ms 5008 KB 
#include "bits/stdc++.h"

using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;

const int inf = 1e9;

template<class T>
struct SegTree {
	vector<T> st;
	int n;
	
	SegTree(int n) : n {n} {
		st.assign(2 * n + 1, 0);
	}
	
	void upd(int k, T x) {
		k += n;
		st[k] = x;
		for(k /= 2; k > 0; k /= 2) st[k] = max(st[2 * k], st[2 * k + 1]);
	}
	
	T query(int l, int r) {
		T ans {};
		for(l += n, r += n; l <= r; l /= 2, r /= 2) {
			if(l & 1) ans = max(ans, st[l++]);
			if(~r & 1) ans = max(ans, st[r--]);
		}
		return ans;
	}
};

void solve() {
	int n, q;
	string s;
	
	cin >> n >> q >> s;
	
	SegTree<int> st(n);
	
	for(int i = 0; i < n; ++i) {
		if(s[i] == '1') st.upd(i, 0);
		else st.upd(i, inf);
	}
	
	for(int i = 1; i <= q; ++i) {
		string type;
		int l, r;
		cin >> type >> l;
		--l;
		if(type == "toggle") {
			if(s[l] == '0') st.upd(l, i);
			else st.upd(l, inf);
			s[l] ^= 1;
		} else {
			cin >> r;
			r -= 2;
			cout << max(0, i - st.query(l, r)) << '\n';
		}
	}
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
 	return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 708 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 89 ms 3088 KB Output is correct
6 Correct 120 ms 3180 KB Output is correct
7 Correct 144 ms 3364 KB Output is correct
8 Correct 172 ms 5008 KB Output is correct
9 Correct 80 ms 1156 KB Output is correct
10 Correct 116 ms 1192 KB Output is correct
11 Correct 90 ms 1228 KB Output is correct
12 Correct 186 ms 3676 KB Output is correct
13 Correct 229 ms 4996 KB Output is correct

Subtask #4
0 / 20.0

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