제출 #1017791

#제출 시각아이디문제언어결과실행 시간메모리
1017791KN200711Election (BOI18_election)C++14
0 / 100
2 ms600 KiB
# include <bits/stdc++.h> # define ll long long # define ld double # define fi first # define se second # define pll pair<ll, ll> using namespace std; int val[500001]; int seg[2][2000020]; void build(int lf, int rg, int nd) { if(lf == rg) { seg[0][nd] = seg[1][nd] = val[lf]; } else { int mid = (lf + rg) / 2; build(lf, mid, 2*nd+1); build(mid+1, rg, 2*nd+2); seg[0][nd] = max(seg[0][2*nd + 1], seg[0][2 * nd + 2]); seg[1][nd] = min(seg[1][2*nd+1], seg[1][2 * nd + 2]); } } int qry(int lf, int rg, int nd, int clf, int crg, int ty) { if(lf > crg || clf > rg) { if(ty == 0) return -1e9; return 1e9; } else if(clf <= lf && rg <= crg) return seg[ty][nd]; int mid = (lf + rg) / 2; if(ty == 0) return max(qry(lf, mid, 2*nd+1, clf, crg, ty), qry(mid+1, rg, 2*nd+2, clf, crg, ty)); else return min(qry(lf, mid, 2*nd+1, clf, crg, ty), qry(mid+1, rg, 2*nd+2, clf, crg, ty)); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin>>N; string S; cin>>S; for(int i=1;i<=N;i++) { if(S[i - 1] == 'C') val[i] = val[i - 1] + 1; else val[i] = val[i - 1] - 1; } build(0, N, 0); int Q; cin>>Q; while(Q--) { int L, R; cin>>L>>R; int mx = qry(0, N, 0, L, R, 0); int mn = qry(0, N, 0, L, R, 1); int fr = val[L - 1]; int lst = val[R]; cout<<max(mx - lst, -(mn - fr))<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...