Submission #1031896

#TimeUsernameProblemLanguageResultExecution timeMemory
1031896stdfloatStreet Lamps (APIO19_street_lamps)C++17
20 / 100
206 ms13484 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; vector<int> st; int upd(int nd, int l, int r, int x, int vl) { if (r < x || x < l) return st[nd]; if (l == r) return st[nd] = vl; int ch = (nd << 1) + 1, md = (l + r) >> 1; return st[nd] = max(upd(ch, l, md, x, vl), upd(ch + 1, md + 1, r, x, vl)); } int fnd(int nd, int l, int r, int x, int y) { if (r < x || y < l) return 0; if (x <= l && r <= y) return st[nd]; int ch = (nd << 1) + 1, md = (l + r) >> 1; return max(fnd(ch, l, md, x, y), fnd(ch + 1, md + 1, r, x, y)); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; string s; cin >> n >> q >> s; st.assign(n << 2, INT_MAX); for (int i = 0; i < n; i++) { if (s[i] == '1') upd(0, 0, n - 1, i, 0); } for (int z = 1; z <= q; z++) { string t; cin >> t; if (t == "toggle") { int i; cin >> i; i--; upd(0, 0, n - 1, i, z); } else { int a, b; cin >> a >> b; a--; b--; cout << z - min(z, fnd(0, 0, n - 1, a, b - 1)) << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...