Submission #1178769

#TimeUsernameProblemLanguageResultExecution timeMemory
1178769pcheloveksElection (BOI18_election)C++20
0 / 100
8 ms320 KiB
//#pragma GCC optimize("Ofast") //#pragma GCC optimize ("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4") //#pragma GCC target("bmi,bmi2,popcnt,lzcnt") #include <iostream> #include <vector> #include <string> #include <map> #include <set> #include <cmath> #include <fstream> #include <climits> #include <queue> #include <algorithm> #include <stdint.h> #include <stack> #include <iomanip> #include <unordered_set> #include <unordered_map> #include <cstring> // Для memset #define endl '\n' using namespace std; typedef long long ll; typedef long double ld; typedef pair <ll, ll> pii; typedef pair <ld, ld> pdd; const ll DIM = 700007; const ll MXMASK = (1 << 21); const ll INF = 1e18; const ll mod = 998244353; const ld eps = 0.00000000001; const ld gr = (sqrt(5) + 1) / 2; const ll offset = 10000; const ll Bits = 20; const ll dx[4] = { 1, 0, -1, 0 }; const ll dy[4] = { 0, 1, 0, -1 }; FILE* stream; ll n, q; string s; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen_s(&stream, "input.txt", "r", stdin); //freopen_s(&stream, "output.txt", "w", stdout); cin >> n; cin >> s; cin >> q; for (int i = 1; i <= q; i++) { ll L, R; deque < pair < char, ll > > d; cin >> L >> R; ll tc = 0; for (int j = L - 1; j < R; j++) { if (d.empty()) { d.push_back({ s[j], 1 }); } else if (d.back().first == s[j]) d.back().second++; else d.push_back({ s[j], 1 }); if (s[j] == 'T') tc++; } ll res = 0, del = 0; while (del < tc) { if (d.size() == 1) { if (d.front().first == 'T') res += d.front().second; break; } else if (d.front().first == 'T') { while (del < tc && d.front().second > 0) { del++; res++; d.front().second--; } d.pop_front(); } else if (d.back().first == 'T') { while (del < tc && d.back().second > 0) { del++; res++; d.back().second--; } d.pop_back(); } else { del += (d.front().second, d.back().second); if (d.front().second == d.back().second) { d.pop_front(); d.pop_back(); } else if (d.front().second < d.back().second) d.pop_front(); else d.pop_back(); } } cout << res << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...