Submission #734717

#TimeUsernameProblemLanguageResultExecution timeMemory
734717grossly_overconfidentStreet Lamps (APIO19_street_lamps)C++17
20 / 100
249 ms14508 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' //#define int long long vector<int> t; int traverse(int v, int tl, int tr, int l, int r){ //cout << tl << " " << tr << " " << l << " " << r << endl; if (tl == l && tr == r){ return t[v]; } int tm = (tl + tr) / 2; if (r <= tm){ return traverse(v * 2, tl, tm, l, r); } if (l >= tm + 1){ return traverse(v * 2 + 1, tm + 1, tr, l, r); } return max(traverse(v * 2, tl, tm, l, tm), traverse(v * 2 + 1, tm + 1, tr, tm + 1, r)); } void update(int v, int tl, int tr, int val, int pos){ if (tl == tr){ t[v] = val; return; } int tm = (tl + tr) / 2; if (pos <= tm){ update(v * 2, tl, tm, val, pos); } if (pos > tm){ update(v * 2 + 1, tm + 1, tr, val, pos); } t[v] = max(t[v * 2], t[v * 2 + 1]); } signed main(){ cin.tie(0); iostream::sync_with_stdio(0); int n, q; cin >> n >> q; t.resize(n * 4); string lamps; cin >> lamps; for (int i = 0; i < n; ++i){ if (lamps[i] == '1'){ update(1, 0, n - 1, 0, i); } else{ update(1, 0, n - 1, 400000, i); } } vector<int> l(n); for (int i = 0; i < n; ++i){ if (lamps[i] == '0'){ l[i] = 400000; } } for (int i = 0; i < q; ++i){ string s; int a, b; cin >> s; if (s == "toggle"){ cin >> a; update(1, 0, n - 1, i + 1, a - 1); } else{ cin >> a >> b; int out = traverse(1, 0, n - 1, a - 1, b - 2); //cout << "debug: " << out << endl; if (out == 400000){ cout << 0 << endl; } else{ cout << i - out + 1 << endl; } } } return 0; }
#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...