// Andrei-Costin Constantinescu
// O(NlogN)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 500000 + 5;
int N, v[NMAX];
struct Node {
int l, r;
int sum, minSuf;
Node(): l(-1), r(-1), sum(-1), minSuf(-1) {}
Node(int _l, int _r, int _sum, int _minSuf): l(_l), r(_r), sum(_sum), minSuf(_minSuf) {}
static Node singleNode(const int l, const int r, const int val) {
return Node(l, r, val, min(val, 0));
}
friend Node operator+(const Node &arg0, const Node &arg1) {
if (arg0.r == -1)
return arg1;
return Node(arg0.l, arg1.r, arg0.sum + arg1.sum, min(arg0.minSuf + arg1.sum, arg1.minSuf));
}
};
const int SQRT = 500;
Node buckets[NMAX / SQRT + 5];
inline int bucketLeft(int bucket) { return (bucket - 1) * SQRT + 1; }
inline int bucketRight(int bucket) { return min(N, bucket * SQRT); }
inline int whichBucket(int pos) { return (pos - 1) / SQRT + 1; }
void buildBucket(int bucket) {
const int l = bucketLeft(bucket), r = bucketRight(bucket);
buckets[bucket] = Node();
for (int i = l; i <= r; ++ i)
buckets[bucket] = buckets[bucket] + Node :: singleNode(i, i, v[i]);
}
void updatePos(int where, int addent) {
v[where] += addent;
buildBucket(whichBucket(where));
}
Node query(int l, int r) {
Node ans;
while (l <= r) {
const int b = whichBucket(l);
if (l == bucketLeft(b) && l + SQRT - 1 <= r) {
ans = ans + buckets[b];
l += SQRT;
}
else {
ans = ans + Node :: singleNode(l, l, v[l]);
l += 1;
}
}
return ans;
}
struct Query {
int r, pos;
Query(int _r = 0, int _pos = 0):
r(_r), pos(_pos) {}
};
vector <Query> queries[NMAX];
int answers[NMAX];
int main() {
cin >> N;
assert(1 <= N && N <= 500000);
string votes;
cin >> votes;
assert(static_cast <int>(votes.size()) == N);
for (int i = 1; i <= N; ++ i) {
assert(votes[i - 1] == 'C' || votes[i - 1] == 'T');
v[i] = votes[i - 1] == 'C' ? 1 : -1;
}
for (int b = 1; b <= whichBucket(N); ++ b)
buildBucket(b);
int Q = 0;
cin >> Q;
assert(1 <= Q && Q <= 500000);
for (int i = 1; i <= Q; ++ i) {
int l, r;
cin >> l >> r;
assert(1 <= l && l <= r && r <= N);
queries[l].emplace_back(r, i);
}
vector <int> stk;
for (int i = N; i; -- i) {
if (v[i] == -1) {
stk.push_back(i);
updatePos(i, 1);
}
else {
if (!stk.empty()) {
updatePos(stk.back(), -1);
stk.pop_back();
}
}
for (auto qr: queries[i]) {
const int l = i, r = qr.r;
answers[qr.pos] = upper_bound(stk.rbegin(), stk.rend(), r) - stk.rbegin() - query(l, r).minSuf;
}
}
for (int i = 1; i <= Q; ++ i)
cout << answers[i] << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
12152 KB |
Output is correct |
2 |
Correct |
21 ms |
12264 KB |
Output is correct |
3 |
Correct |
26 ms |
12264 KB |
Output is correct |
4 |
Correct |
24 ms |
12400 KB |
Output is correct |
5 |
Correct |
26 ms |
12400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
12152 KB |
Output is correct |
2 |
Correct |
21 ms |
12264 KB |
Output is correct |
3 |
Correct |
26 ms |
12264 KB |
Output is correct |
4 |
Correct |
24 ms |
12400 KB |
Output is correct |
5 |
Correct |
26 ms |
12400 KB |
Output is correct |
6 |
Correct |
519 ms |
14720 KB |
Output is correct |
7 |
Correct |
474 ms |
14720 KB |
Output is correct |
8 |
Correct |
447 ms |
14720 KB |
Output is correct |
9 |
Correct |
416 ms |
14720 KB |
Output is correct |
10 |
Correct |
407 ms |
14720 KB |
Output is correct |
11 |
Correct |
537 ms |
15104 KB |
Output is correct |
12 |
Correct |
395 ms |
15104 KB |
Output is correct |
13 |
Correct |
472 ms |
15152 KB |
Output is correct |
14 |
Correct |
351 ms |
15152 KB |
Output is correct |
15 |
Correct |
457 ms |
15152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
12152 KB |
Output is correct |
2 |
Correct |
21 ms |
12264 KB |
Output is correct |
3 |
Correct |
26 ms |
12264 KB |
Output is correct |
4 |
Correct |
24 ms |
12400 KB |
Output is correct |
5 |
Correct |
26 ms |
12400 KB |
Output is correct |
6 |
Correct |
519 ms |
14720 KB |
Output is correct |
7 |
Correct |
474 ms |
14720 KB |
Output is correct |
8 |
Correct |
447 ms |
14720 KB |
Output is correct |
9 |
Correct |
416 ms |
14720 KB |
Output is correct |
10 |
Correct |
407 ms |
14720 KB |
Output is correct |
11 |
Correct |
537 ms |
15104 KB |
Output is correct |
12 |
Correct |
395 ms |
15104 KB |
Output is correct |
13 |
Correct |
472 ms |
15152 KB |
Output is correct |
14 |
Correct |
351 ms |
15152 KB |
Output is correct |
15 |
Correct |
457 ms |
15152 KB |
Output is correct |
16 |
Execution timed out |
3052 ms |
27468 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |