#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define endl "\n"
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define pi 3.14159265359
#define TASKNAME "election"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
* str = C C C T T T T T T C C
* 1 1 1 -1 -1 -1 -1 -1 -1 1 1
* 1 2 3 2 1 0 -1 -2 -3 -2 -1
*
* Ta vote tu phai sang trai va tu trai sang phai
* Ta can loai bo it nhat cac la phieu cho tai moi thoi diem du duyet tu trai hay phai, ta
* deu co the delta >= 0.
*
* Nhung bai nhu nay ta se nghi den co che + / - nhu day ngoac
* Goi left[i]: so vi tri j (j <= i) chua ki tu T ta can tac dong sao cho vi tri i tro thanh gia tri duong
* right[i]: so vi tri j (j >= i) chua ki tu T ta can tac dong sao cho vi tri i tro thanh gia tri duong
*
* Voi bai nay thi bam vao dau de giai nhi
* Dua vao left[i], right[i]:
* Ta can tim tap vi tri {T1, T2, ..., Tk} sao cho khi xoá hết T1, T2, ... Tk thì giá trị của các vị trí left[i] và
* right[i] sẽ dương.
* Giai bang dp:
*
* Sol:
* Có 2 solution:
* 1 - Tham lam: Với 1 đoạn [l, r], ta duyệt từ trái sang phải, Nếu vị trí đó âm thì ta phải xóa vị trí đó
* đi.
* - Ta tiếp tục đi từ phải sang trái và làm điều tương tự.
*
* Khi xử lý offline, ta sẽ di chuyển từ phải sang trái.
**/
int n, q;
string str;
const int MAXN = 3e5 + 9;
namespace subtask1{
bool check(){
return n <= 2000 and q <= 2000;
}
bool del[2003];
int get(int l, int r){
int deltaLeft = 0;
int deltaRight = 0;
int ans = 0;
fill(del + l, del + 1 + r, false);
for(int i = 1; i <= r - l + 1; i++){
int leftPtr = l + i - 1;
if (!del[leftPtr]){
if (str[leftPtr] == 'C'){
deltaLeft++;
}
else deltaLeft--;
if (deltaLeft < 0) del[leftPtr] = true, deltaLeft++,ans++;
}
}
for(int i = 1; i <= r - l + 1; i++){
int rightPtr = r - i + 1;
if (!del[rightPtr]){
if (str[rightPtr] == 'C'){
deltaRight++;
}
else deltaRight--;
if (deltaRight < 0) del[rightPtr] = true, deltaRight++,ans++;
}
}
return ans;
}
void solve(){
for(int i = 1; i <= q; i++){
int l, r;
cin >> l >> r;
int ans = get(l, r);
cout << ans << endl;
}
}
}
namespace subtask2{
bool check(){
return true;
}
vector<int> stk;
vector<ii> Query[MAXN];
//Duyet tu phai sang trai.
//Ta duy tri nhung thang se bi xoa o khi di tu trai sang - Ta se dung 1 cai stack de duy tri nhung vi tri do
//Tu ben phai, ta se dung 1 cay segment tree de tim vi tri co tong lon nhat va la 1 suffix.
int st[MAXN << 2], lazy[MAXN << 2], ans[MAXN];
void fix(int nn, int l, int r){
if (lazy[nn] != 0){
st[nn] += lazy[nn];
if (l != r) {
lazy[nn << 1] += lazy[nn];
lazy[nn << 1 | 1] += lazy[nn];
}
lazy[nn] = 0;
}
}
void updateRange(int nn, int l, int r, int u, int v, int k){
fix(nn, l, r);
if (l >= u and r <= v){
lazy[nn] += k;
fix(nn, l, r);
return;
}
if (l > v or r < u) return;
int mid = (l + r) >> 1;
updateRange(nn << 1, l, mid, u, v, k);
updateRange(nn << 1 | 1, mid + 1, r, u, v, k);
st[nn] = min(st[nn << 1], st[nn << 1 | 1]);
}
int getMin(int nn, int l, int r, int u, int v){
fix(nn, l, r);
if (l >= u and r <= v) return st[nn];
if (l > v or r < u) return inf;
int mid = (l + r) >> 1;
return min(getMin(nn << 1, l, mid, u, v),
getMin(nn << 1 | 1, mid + 1, r, u, v));
}
int countRange(vector<int> &lmao, int x){
int l = 0, r = lmao.size() - 1, res = lmao.size();
while(l <= r){
int mid = (l + r) >> 1;
if (lmao[mid] <= x){
r = mid - 1;
res = mid;
}
else l = mid + 1;
}
return lmao.size() - res;
}
void solve(){
for(int i = 1; i <= q; i++){
int l, r;
cin >> l >> r;
Query[l].pb({r, i});
}
memset(st, 0, sizeof(st));
int len = str.length() - 1;
for(int i = len; i >= 1; i--){
if (str[i] == 'T') stk.pb(i);
else if (!stk.empty()){
int x = stk.back();
updateRange(1, 1, n, 1, x, -1);
stk.pop_back();
}
if (str[i] == 'C') {
updateRange(1, 1, n + 1, 1, i, 1);
}
// cout << "CUR: " << i << endl;
// for(int j = i; j <= len; j++){
// cout << getMin(1, 1, n + 1, j, j) << ' ';
// }
// cout << endl;
// for(auto x: stk){
// cout << x << ' ';
// }
// cout << endl;
for(auto [r, id]: Query[i]){
// cout << i << ' ' << r << endl;
// cout << countRange(stk, r) << ' ' << getMin(1, 1, n + 1, i, r) << ' ' << getMin(1, 1, n + 1, r + 1, r + 1 ) << endl;
int range = getMin(1, 1, n + 1, i, r) - getMin(1, 1, n + 1, r + 1, r + 1);
ans[id] = countRange(stk, r) + ((range < 0) ? abs(range) : 0);
}
// cout << endl;
}
for(int i = 1; i <= q; i++){
cout << ans[i] << endl;
}
}
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> n;
cin >> str;
str = '#' + str;
cin >> q;
if (subtask1::check()) return subtask1::solve(), 0;
if (subtask2::check()) return subtask2::solve(), 0;
}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
**/
Compilation message
election.cpp:209:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
209 | main()
| ^~~~
election.cpp: In function 'int main()':
election.cpp:213:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
213 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:214:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
214 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7516 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7516 KB |
Output is correct |
| 4 |
Correct |
5 ms |
7516 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7516 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7516 KB |
Output is correct |
| 4 |
Correct |
5 ms |
7516 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7512 KB |
Output is correct |
| 6 |
Incorrect |
67 ms |
22412 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7516 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7516 KB |
Output is correct |
| 4 |
Correct |
5 ms |
7516 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7512 KB |
Output is correct |
| 6 |
Incorrect |
67 ms |
22412 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
