제출 #951247

#제출 시각아이디문제언어결과실행 시간메모리
951247vjudge1Election (BOI18_election)C++17
0 / 100
1 ms604 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 5e5 + 5; const int M = 19; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { char c; cin >> c; a[i] = 1 - 2 * (c == 'T'); } vector<int> pre(n + 1), suf(n + 2); for (int i = 0; i < n; i++) { pre[i + 1] = pre[i] + a[i]; } for (int i = n - 1; i >= 0; i--) { suf[i + 1] = suf[i + 2] + a[i]; } int sp1[n + 1][M], sp2[n + 1][M]; for (int i = 1; i <= n; i++) { sp1[i][0] = pre[i], sp2[i][0] = suf[i]; } for (int j = 1; j < M; j++) { for (int i = 1; i <= n; i++) { int nxt = min(n, i + (1 << (j - 1))); sp1[i][j] = min(sp1[i][j - 1], sp1[nxt][j - 1]); sp2[i][j] = min(sp2[i][j - 1], sp2[nxt][j - 1]); } } int q; cin >> q; while (q--) { int l, r; cin >> l >> r; int lg = 31 - __builtin_clz(r - l + 1); int a1 = min(sp1[l][lg], sp1[r - (1 << lg) + 1][lg]) - pre[l - 1]; int a2 = min(sp2[l][lg], sp2[r - (1 << lg) + 1][lg]) - suf[r + 1]; cout << max(0, -min(a1, a2)) << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...