제출 #167548

#제출 시각아이디문제언어결과실행 시간메모리
167548qkxwsmStreet Lamps (APIO19_street_lamps)C++14
20 / 100
308 ms16524 KiB
#include <bits/stdc++.h> using namespace std; template<class T, class U> void ckmin(T &a, U b) { if (a > b) a = b; } template<class T, class U> void ckmax(T &a, U b) { if (a < b) a = b; } #define MP make_pair #define PB push_back #define LB lower_bound #define UB upper_bound #define fi first #define se second #define FOR(i, a, b) for (auto i = (a); i < (b); i++) #define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--) #define SZ(x) ((int) (x).size()) #define ALL(x) (x).begin(), (x).end() #define MAXN 351313 typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vpi; typedef vector<pll> vpl; int N, Q; int stor[MAXN]; int lst[MAXN]; pii quer[MAXN]; bitset<MAXN> state; int seg[3 * MAXN]; void update(int w, int L, int R, int a, int t) { if (L == R) { seg[w] = t; return; } int mid = (L + R) >> 1; if (a <= mid) { update(w << 1, L, mid, a, t); } else { update(w << 1 | 1, mid + 1, R, a, t); } seg[w] = max(seg[w << 1], seg[w << 1 | 1]); } int query(int w, int L, int R, int a, int b) { if (a <= L && R <= b) { return seg[w]; } int mid = (L + R) >> 1, res = -69; if (a <= mid) { ckmax(res, query(w << 1, L, mid, a, b)); } if (mid < b) { ckmax(res, query(w << 1 | 1, mid + 1, R, a, b)); } return res; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(12); cerr << fixed << setprecision(4); cin >> N >> Q; string temps; cin >> temps; FOR(i, 0, N) { state[i] = (temps[i] == '1'); lst[i] = -1; if (state[i]) { update(1, 0, N - 1, i, -1); } else { update(1, 0, N - 1, i, Q + 1); } } FOR(i, 0, Q) { cin >> temps; int x, y; if (temps[0] == 't') { cin >> x; x--; quer[i] = {-1, x}; } else { cin >> x >> y; x--; y -= 2; quer[i] = {x, y}; } } FOR(i, 0, Q) { if (quer[i].fi == -1) { int idx = quer[i].se; update(1, 0, N - 1, idx, i); } else { int lt = quer[i].fi, rt = quer[i].se; int mn = query(1, 0, N - 1, lt, rt); if (mn > i) { cout << "0\n"; } else { cout << i - mn << '\n'; } } } //for each guy, store: when was i turned on? 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...