Submission #1040908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040908		Requiem	Election (BOI18_election)	C++17	28 / 100	4 ms	856 KiB

election

#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
**/

Compilation message (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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 28 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18