Submission #479648

#TimeUsernameProblemLanguageResultExecution timeMemory
479648CodeChamp_SSElection (BOI18_election)C++17
100 / 100
564 ms28104 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define ff first #define ss second #define pb push_back #define eb emplace_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define setbits(x) __builtin_popcountll(x) #define zrobits(x) __builtin_ctzll(x) #define sz(v) (int)v.size() #define ps(y) cout << fixed << setprecision(y) #define ms(arr, v) memset(arr, v, sizeof(arr)) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define trav(x, v) for(auto &x: v) #define w(t) int t; cin >> t; while(t--) #define rep(i, a, b) for(int i = a; i <= b; i++) #define rrep(i, a, b) for(int i = a; i >= b; i--) #define rep0(i, n) rep(i, 0, n - 1) #define rrep0(i, n) rrep(i, n - 1, 0) #define rep1(i, n) rep(i, 1, n) #define rrep1(i, n) rrep(i, n, 1) #define inp(arr, n) rep0(i, n) cin >> arr[i]; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pii; typedef vector<ll> vi; typedef vector<vi> vvi; typedef vector<pii> vp; typedef vector<bool> vb; typedef vector<string> vs; typedef map<ll, ll> mii; typedef map<char, ll> mci; typedef priority_queue<ll> pq_mx; typedef priority_queue<ll, vi, greater<>> pq_mn; typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> pbds; /* * find_by_order(i) -> returns an iterator to the element at ith position (0 based) * order_of_key(i) -> returns the position of element i (0 based) */ const int N = 5e5 + 5; const int mod = 1e9 + 7; //const int mod = 998244353; const ll inf = 2e18; const ld eps = 1e-10, pi = acos(-1.0); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void fio() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); } ll n, q; string S; struct Node { int lmx = 0, rmx = 0, sum = 0, mx = 0; }; struct SegTree { Node st[4 * N]{}, dummy{}; Node combine(Node l, Node r) { return { max(l.lmx, l.sum + r.lmx), max(r.rmx, r.sum + l.rmx), l.sum + r.sum, max(l.lmx + r.rmx, max(l.mx + r.sum, l.sum + r.mx)) }; } void build(ll s = 0, ll e = n - 1, int idx = 1) { if (s == e) { st[idx] = ((S[s] == 'T') ? Node{1, 1, 1, 1} : Node{0, 0, -1, 0}); return; } ll m = s + (e - s) / 2; build(s, m, 2 * idx), build(m + 1, e, 2 * idx + 1); st[idx] = combine(st[2 * idx], st[2 * idx + 1]); } Node query(ll qs, ll qe, ll s = 0, ll e = n - 1, int idx = 1) { if (qs > e or qe < s) return dummy; if (s >= qs and e <= qe) return st[idx]; ll mid = s + (e - s) / 2; Node lft = query(qs, qe, s, mid, 2 * idx), rt = query(qs, qe, mid + 1, e, 2 * idx + 1); return combine(lft, rt); } } st; int main() { fio(); cin >> n >> S >> q; st.build(); rep0(x, q) { int l, r; cin >> l >> r, --l, --r; cout << st.query(l, r).mx << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...