Submission #216400

#TimeUsernameProblemLanguageResultExecution timeMemory
216400usachevd0Street Lamps (APIO19_street_lamps)C++14
40 / 100
152 ms8948 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef long double ld; void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } #ifdef DEBUG #define time(...) 42 #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; } const int maxN = 300005; char a0[maxN]; pii que[maxN]; signed main() { #ifdef DEBUG freopen("in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; if (n <= 100 && q <= 100) { char t[q + 1][n]; memset(t, 0, sizeof(t)); string s; cin >> s; for (int i = 0; i < n; ++i) t[0][i] = s[i] - '0'; for (int i = 1; i <= q; ++i) { memcpy(t[i], t[i - 1], sizeof(t[i])); string cmd; cin >> cmd; if (cmd == "toggle") { int j; cin >> j; --j; t[i][j] ^= 1; } else { int l, r; cin >> l >> r; r -= 2; l--; int ans = 0; for (int u = 0; u < i; ++u) { bool ok = true; for (int j = l; j <= r; ++j) { ok &= t[u][j]; } if (ok) ++ans; } cout << ans << '\n'; } } exit(0); } // normal string tmp; cin >> tmp; for (int i = 0; i < n; ++i) a0[i] = tmp[i] - '0'; bool all_ones = true; bool toggle_to_one = true; int _a[n]; for (int i = 0; i < n; ++i) _a[i] = a0[i]; for (int t = 1; t <= q; ++t) { string cmd; cin >> cmd; auto &q = que[t]; if (cmd == "toggle") { q.se = -1; cin >> q.fi; q.fi--; int i = q.fi; _a[i] ^= 1; toggle_to_one &= _a[i] == 1; } else { cin >> q.fi >> q.se; q.fi--; q.se -= 2; all_ones &= q.fi == q.se; } } if (all_ones) { int when[n], sum[n]; memset(when, 0, sizeof(when)); memset(sum, 0, sizeof(sum)); for (int t = 1; t <= q; ++t) { auto &q = que[t]; if (q.se == -1) { int i = q.fi; if (a0[i] == 0) { when[i] = t; } else { sum[i] += t - when[i]; } a0[i] ^= 1; } else { int i = q.fi; cout << sum[i] + (a0[i] == 1 ? t - when[i] : 0) << '\n'; } } exit(0); } if (toggle_to_one) { int when[n]; memset(when, 0x3f, sizeof(when)); for (int t = 1; t <= q; ++t) { auto &q = que[t]; if (q.se == -1) { int i = q.fi; when[i] = t; } } const int logN = 19; const int N = 1 << logN; int sgt[2 * N]; memset(sgt, 0x3f, sizeof(sgt)); for (int i = 0; i < n; ++i) { sgt[i + N] = when[i]; } for (int v = N - 1; v >= 1; --v) { sgt[v] = max(sgt[v << 1], sgt[v << 1 | 1]); } for (int t = 1; t <= q; ++t) { auto &q = que[t]; if (q.se != -1) { int l = q.fi; int r = q.se; int mx = -1e9; for (int L = l, R = r; L <= R; L >>= 1, R >>= 1) { if (L & 1) chkmax(mx, sgt[L++]); if (!R & 1) chkmax(mx, sgt[R--]); } cout << max(0, t - mx) << '\n'; } } exit(0); } 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...