Submission #1174683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174683		tkm_algorithms	Street Lamps (APIO19_street_lamps)	C++20	0 / 100	49 ms	1348 KiB

street_lamps

/**
*    In the name of Allah
*    We are nothing and you're everything
*    author: najmuddin
**/
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
#define int ll
const char nl = '\n';
const int N = 101;
const int inf = 1e9;

struct st {
	int dlit;
	int last;
	int ok;
};

struct segtree {
	vector<int> tree;
	int size;
	
	void init(int n) {
		size = 1;
		while (size < n)size <<= 1;
		tree.assign(2*size-1, inf);
	}
	
	void set(int i, int v, int x, int lx, int rx) {
		if (rx - lx == 1) {
			tree[x] = v;
			return;
		}
		
		int mid = (lx + rx) >> 1;
		if (i < mid)set(i, v, 2*x+1, lx, mid);
		else set(i, v, 2*x+2, mid, rx);
		tree[x] = min(tree[2*x+1], tree[2*x+2]);
	}
	
	void set(int i, int v) {
		set(i, v, 0, 0, size);
	}
	
	int get(int l, int r, int x, int lx, int rx) {
		if (lx >= l && rx <= r)return tree[x];
		if (rx <= l || r <= lx)return inf;
		
		int mid = (lx + rx) >> 1;
		int m1 = get(l, r, 2*x+1, lx, mid);
		int m2 = get(l, r, 2*x+2, mid, rx);
		return min(m1, m2);
	}
	
	int get(int l, int r) {
		return get(l, r, 0, 0, size);
	}
};

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, q; cin >> n >> q;
	
	string s; cin >> s;
	s = '&'+s;
	
	segtree st;
	st.init(n+1);
	
	for (int i = 1; i <= n; ++i) {
		if (s[i] == '0')st.set(i, -inf);
	}
	
	for (int _ = 1; _ <= q; ++_) {
		string tp; cin >> tp;
		if (tp == "toggle") {
			int pos; cin >> pos;
			st.set(pos, _);
		} else {
			int a, b; cin >> a >> b;
			int ans = st.get(a, b);
			ans = min(ans, _);
			ans = max(ans, 0ll);
			cout << ans << nl;
		}
	}
	return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20