이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 ""
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;
int n, q;
string str;
namespace subtask1{
bool check(){
return n <= 2000 and q <= 2000;
}
bool del[2003];
/**
* 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:
**/
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;
}
}
}
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;
}
/**
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
**/
컴파일 시 표준 에러 (stderr) 메시지
election.cpp:90:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
90 | main()
| ^~~~
election.cpp: In function 'int main()':
election.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |