Submission #1265587

#TimeUsernameProblemLanguageResultExecution timeMemory
1265587PlayVoltzElection (BOI18_election)C++20
100 / 100
540 ms82032 KiB
#include <cstdio> #include <stdio.h> #include <stdbool.h> #include <iostream> #include <map> #include <vector> #include <climits> #include <stack> #include <string> #include <queue> #include <algorithm> #include <set> #include <unordered_set> #include <unordered_map> #include <cmath> #include <cctype> #include <bitset> #include <iomanip> #include <cstring> #include <numeric> #include <cassert> using namespace std; #define int long long #define pii pair<int, int> #define mp make_pair #define pb push_back #define fi first #define se second string ss; struct ooga{ int t, l, r, mx; }; ooga merge(ooga l, ooga r){ ooga res; res.t=l.t+r.t; res.l=max(l.l, l.t+r.l); res.r=max(r.r, r.t+l.r); res.mx=max({l.l+r.r, l.t+r.mx, r.t+l.mx}); return res; } struct node{ int s, e, m; ooga val; node *l, *r; node(int S, int E){ s = S, e = E, m = (s+e)/2; if (s!=e){ l = new node(s, m); r = new node(m+1, e); val=merge(l->val, r->val); } else if (ss[s]=='T')val={1, 1, 1, 1}; else val={-1, 0, 0, 0}; } ooga query(int left, int right){ if (s==left && e==right)return val; if (right<=m)return l->query(left, right); else if (left>m)return r->query(left, right); else return merge(l->query(left, m), r->query(m+1, right)); } }*st; int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q, a, b; cin>>n>>ss; ss=" "+ss; st = new node(1, n); cin>>q; while (q--)cin>>a>>b, cout<<st->query(a, b).mx<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...