oj.uz

Submission #475549

# Submission time Handle Problem Language Result Execution time Memory
475549 2021-09-22T21:45:49 Z thiago_bastos Street Lamps (APIO19_street_lamps) C++17
20 / 100
 202 ms 12168 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>;

template<class T>
struct BIT {
	vector<T> bit;
	
	BIT(int n) {
		bit.assign(n + 1, 0);
	}
	
	void upd(int k, T x) {
		for(++k; k < int(bit.size()); k += k & -k) bit[k] += x;
	}
	
	T query(int k) {
		T ans {};
		for(++k; k > 0; k -= k & -k) ans += bit[k];
		return ans;
	}
	
	T query(int l, int r) {
		if(l > r) return (T)0;
		return query(r) - query(l - 1);
	}
};

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;
	
	BIT<int> bit(n);
	SegTree<int> st(n);
	
	for(int i = 0; i < n; ++i) bit.upd(i, s[i] - '0');
	
	for(int i = 1; i <= q; ++i) {
		string type;
		int l, r;
		cin >> type >> l;
		--l;
		if(type == "toggle") {
			int x = s[l] - '0';
			bit.upd(l, (x ^ 1) - x);
			st.upd(l, i);
			s[l] ^= 1;
		} else {
			cin >> r;
			r -= 2;
			if(bit.query(l, r) == r - l + 1) cout << i - st.query(l, r) << '\n';
			else cout << "0\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 81 ms 796 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 320 KB Output is correct
5 Correct 109 ms 4248 KB Output is correct
6 Correct 116 ms 4328 KB Output is correct
7 Correct 118 ms 4528 KB Output is correct
8 Correct 199 ms 12164 KB Output is correct
9 Correct 71 ms 3880 KB Output is correct
10 Correct 72 ms 4240 KB Output is correct
11 Correct 81 ms 4368 KB Output is correct
12 Correct 113 ms 10696 KB Output is correct
13 Correct 202 ms 12168 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 -