제출 #942788

#제출 시각아이디문제언어결과실행 시간메모리
94278812345678Election (BOI18_election)C++17
0 / 100
11 ms33372 KiB
#include <bits/stdc++.h> using namespace std; const int nx=5e5+5; int n, vl[nx], q, l, r; string str; struct segtree { struct node { int l, r, sm, ans; node(): l(0), r(0), sm(0), ans(-1e9){} node(int x): l(x), r(x), sm(x), ans(x==1){} friend node operator+(const node &a, const node &b) { if (a.ans==-1e9) return b; if (b.ans==-1e9) return a; node res; res.l=max(a.l, a.sm+b.l); res.r=max(a.r+b.sm, b.r); res.sm=a.sm+b.sm; res.ans=max({a.ans+b.sm, a.sm+b.ans, a.l+b.r, 0}); return res; } } d[4*nx]; void build(int l, int r, int i) { if (l==r) return d[i]=node(vl[l]), void(); int md=(l+r)/2; build(l, md, 2*i); build(md+1, r, 2*i+1); d[i]=d[2*i]+d[2*i+1]; //cout<<l<<' '<<r<<' '<<d[i].l<<' '<<d[i].r<<' '<<d[i].sm<<' '<<d[i].ans<<'\n'; } node query(int l, int r, int i, int ql, int qr) { if (qr<l||r<ql) return node(); if (ql<=l&&r<=qr) return d[i]; int md=(l+r)/2; return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr); } } s; int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>str; str=' '+str; for (int i=1; i<=n; i++) vl[i]=(str[i]=='T')?1:-1; s.build(1, n, 1); cin>>q; while (q--) cin>>l>>r, cout<<s.query(1, n, 1, l, r).ans<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...