Submission #1253890

#TimeUsernameProblemLanguageResultExecution timeMemory
1253890armashkaElection (BOI18_election)C++20
28 / 100
3093 ms980 KiB
#include <bits/stdc++.h> #define pb push_back #define all(v) v.begin(), v.end() #define sz(x) (int)(x).size() using namespace std; using ll = long long; using ld = long double; const int N = 1e6 + 5; const ll mod = 1e9 + 7; const ld eps = 1e-6; const ld Pi = acos(-1.0); int n, q; string s; int used[N], timer; void solve() { cin >> n >> s; s = " " + s; // for (int i = 1; i <= n; ++i) // { // pref[i] = pref[i - 1] + (s[i] == 'T'); // } // for (int i = n + 1; i >= 1; --i) // { // suf[i] = suf[i + 1] + (s[i] == 'T'); // } cin >> q; for (int j = 1; j <= q; ++j) { int l, r; cin >> l >> r; int ans = 0, bal = 0; ++timer; for (int i = l; i <= r; ++i) { if (s[i] == 'C') ++bal; else --bal; if (bal < 0) { ++ans; ++bal; used[i] = timer; } } bal = 0; for (int i = r; i >= l; --i) { if (used[i] == timer) continue; if (s[i] == 'C') ++bal; else --bal; if (bal < 0) { ++ans; ++bal; used[i] = timer; } } cout << ans << "\n"; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; // cin >> tt; for (int i = 1; i <= tt; ++i) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...