This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F first
#define S second
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define pb push_back
const int Inf = 2e9 + 10;
const int Mod = 1e9 + 7;
const int LG = 25;
const int SQ = 400;
const int Alpha = 27;
const int maxN = 5e3 + 10;
int n, q;
int a[maxN];
struct SegTree {
struct Node {
int sum;
int mnLR;
int mnRL;
Node() {
sum = 0;
}
} t[maxN<<2];
void initialize(int id, int L, int R) {
if(L+1 == R) {
t[id].sum = a[L];
t[id].mnLR = a[L];
t[id].mnRL = a[L];
return;
}
int mid = (L+R)>>1;
initialize(2*id+0, L, mid);
initialize(2*id+1, mid, R);
t[id].sum = t[2*id+0].sum + t[2*id+1].sum;
t[id].mnLR = min(t[2*id+0].mnLR, t[2*id+0].sum + t[2*id+1].mnLR);
t[id].mnRL = min(t[2*id+1].mnRL, t[2*id+1].sum + t[2*id+0].mnRL);
}
void Get(int id, int L, int R, int l, int r, vector <int> &g) {
if(L == l and R == r) {
g.pb(id);
return;
}
int mid = (L+R)>>1;
if(l < mid)
Get(2*id+0, L, mid, l, min(mid, r), g);
if(r > mid)
Get(2*id+1, mid, R, max(l, mid), r, g);
}
};
int main() {
IOS;
cin >> n;
for(int i = 1; i <= n; i++) {
char c;
cin >> c;
a[i] = -1;
if(c == 'C')
a[i] = 1;
}
SegTree s;
s.initialize(1, 1, n+1);
cin >> q;
while(q--) {
int l, r;
cin >> l >> r;
vector <int> g;
g.clear();
s.Get(1, 1, n+1, l, r+1, g);
int mn1 = Inf;
int mn2 = Inf;
int CurSum = 0;
for(int i = 0; i < sz(g); i++) {
int tmp = s.t[g[i]].mnLR;
tmp += CurSum;
CurSum += s.t[g[i]].sum;
mn1 = min(mn1, tmp);
}
CurSum = 0;
for(int i = sz(g)-1; i >= 0; i--) {
int tmp = s.t[g[i]].mnRL;
tmp += CurSum;
CurSum += s.t[g[i]].sum;
mn2 = min(mn2, tmp);
}
cout << abs(min(0, min(mn1, mn2))) << "\n";
}
}
Compilation message (stderr)
election.cpp: In function 'int main()':
election.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 0; i < sz(g); i++) {
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |