Submission #1042859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042859		Requiem	Election (BOI18_election)	C++17	28 / 100	67 ms	22412 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 "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 (stderr)

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

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