Submission #249023

#TimeUsernameProblemLanguageResultExecution timeMemory
249023SamAndStreet Lamps (APIO19_street_lamps)C++17
60 / 100
1129 ms16724 KiB
#include <bits/stdc++.h> using namespace std; #define m_p make_pair #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define fi first #define se second typedef long long ll; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnf(2106); const int N = 300005; struct ban { char ty; int x, y; }; int n_, q_; char s_[N]; ban a_[N]; void ka() { cin >> n_ >> q_; cin >> s_; for (int i = 0; i < q_; ++i) { char tyy[20]; cin >> tyy; a_[i].ty = tyy[0]; if (tyy[0] == 't') cin >> a_[i].x; else cin >> a_[i].x >> a_[i].y; } } namespace solv1 { const int N = 102; int n, q; char a[N][N], aa[N]; int p[N][N]; void cntp(int i) { for (int j = 1; j <= n; ++j) { p[i][j] = p[i][j - 1]; if (a[i][j] == '1') ++p[i][j]; } } void solv() { n = n_; q = q_; for (int i = 0; i < n; ++i) aa[i] = s_[i]; for (int j = 1; j <= n; ++j) a[0][j] = aa[j - 1]; cntp(0); for (int i = 1; i <= q; ++i) { for (int j = 1; j <= n; ++j) { a[i][j] = a[i - 1][j]; } char ty; ty = a_[i - 1].ty; if (ty == 'q') { int l, r; l = a_[i - 1].x; r = a_[i - 1].y; --r; int ans = 0; for (int ii = 0; ii < i; ++ii) { if (p[ii][r] - p[ii][l - 1] == (r - l + 1)) ++ans; } cout << ans << endl; } else { int x; x = a_[i - 1].x; if (a[i][x] == '0') a[i][x] = '1'; else a[i][x] = '0'; } cntp(i); } } }; namespace solv2 { const int N = 300005; int n, q; char a[N]; int ans[N]; int t[N]; void solv() { n = n_; q = q_; for (int i = 1; i <= n; ++i) { a[i] = s_[i - 1]; if (a[i] == '1') { t[i] = 0; } else t[i] = -1; } for (int j = 1; j <= q; ++j) { char ty; ty = a_[j - 1].ty; if (ty == 'q') { int l, r; l = a_[j - 1].x; r = a_[j - 1].y; if (t[l] == -1) cout << ans[l] << endl; else cout << ans[l] + (j - t[l]) << endl; } else { int i; i = a_[j - 1].x; if (a[i] == '0') { a[i] = '1'; t[i] = j; } else { a[i] = '0'; ans[i] += (j - t[i]); t[i] = -1; } } } } }; namespace solv3 { const int N = 300005; int n, q; char a[N]; int t[N * 4]; void ubd(int tl, int tr, int x, int y, int pos) { if (tl == tr) { t[pos] = y; return; } int m = (tl + tr) / 2; if (x <= m) ubd(tl, m, x, y, pos * 2); else ubd(m + 1, tr, x, y, pos * 2 + 1); t[pos] = max(t[pos * 2], t[pos * 2 + 1]); } int qry(int tl, int tr, int l, int r, int pos) { if (tl == l && tr == r) return t[pos]; int m = (tl + tr) / 2; if (r <= m) return qry(tl, m, l, r, pos * 2); if (l > m) return qry(m + 1, tr, l, r, pos * 2 + 1); return max(qry(tl, m, l, m, pos * 2), qry(m + 1, tr, m + 1, r, pos * 2 + 1)); } void solv() { n = n_; q = q_; for (int i = 1; i <= n; ++i) { a[i] = s_[i - 1]; if (a[i] == '0') ubd(1, n, i, N, 1); else ubd(1, n, i, 0, 1); } for (int i = 1; i <= q; ++i) { char ty; ty = a_[i - 1].ty; if (ty == 'q') { int l, r; l = a_[i - 1].x; r = a_[i - 1].y; --r; int j = qry(1, n, l, r, 1); if (j == N) cout << 0 << endl; else cout << i - j << endl; } else { int x; x = a_[i - 1].x; ubd(1, n, x, i, 1); } } } }; int main() { #ifdef SOMETHING freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); #endif // SOMETHING //ios_base::sync_with_stdio(false), cin.tie(0); ka(); if (n_ <= 100 && q_ <= 100) { solv1::solv(); return 0; } bool z2 = true; for (int i = 0; i < q_; ++i) { if (a_[i].ty == 'q') { if (a_[i].y - a_[i].x != 1) { z2 = false; break; } } } if (z2) { solv2::solv(); } else { solv3::solv(); } return 0; } //while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message (stderr)

street_lamps.cpp: In function 'void solv2::solv()':
street_lamps.cpp:132:24: warning: variable 'r' set but not used [-Wunused-but-set-variable]
                 int l, r;
                        ^
#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...