제출 #957275

#제출 시각아이디문제언어결과실행 시간메모리
957275IcelastElection (BOI18_election)C++17
100 / 100
499 ms44620 KiB
#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 5*1e5+5, INF = 4e18+9; ll n, Q; string s; void inp(){ cin >> n; cin >> s; s = ' ' + s; cin >> Q; } struct Node{ ll L, R, S, res; }; ll N; Node T[4*maxn]; Node merg(Node a, Node b){ Node res; res.S = a.S+b.S; res.L = max(a.L, a.S+b.L); res.R = max(b.R, a.R+b.S); res.res = max(max(a.S+b.res, a.res+b.S), a.L+b.R); return res; } void build_segtree(){ N = 1; while(N < n) N*=2; for(int i = 1; i <= n; i++){ if(s[i] == 'C'){ T[i+N-1] = {0, 0, -1, 0}; }else{ T[i+N-1] = {1, 1, 1, 1}; } } for(int i = n+1; i <= N; i++){ T[i+N-1] = {0, 0, 0, 0}; } for(int i = N-1; i >= 1; i--){ T[i] = merg(T[i*2], T[i*2+1]); } } Node get(int node, int low, int high, int l, int r){ if(low > r || l > high) return {0, 0, 0, 0}; if(low >= l && r >= high) return T[node]; int mid = (low+high)/2; return merg(get(node*2, low, mid, l, r), get(node*2+1, mid+1, high, l, r)); } void solve(){ build_segtree(); int l, r; for(int i = 1; i <= Q; i++){ cin >> l >> r; cout << get(1, 1, N, l, r).res << "\n"; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); inp(); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...