oj.uz

Submission #1042866

# Submission time Handle Problem Language Result Execution time Memory
1042866 2024-08-03T13:27:15 Z Requiem Election (BOI18_election) C++17
100 / 100
 609 ms 65516 KB 
#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 = 5e5 + 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, 1, x, -1);
                 stk.pop_back();
             }

             if (str[i] == 'C') {
                 updateRange(1, 1, n + 1, 1, i, 1);
             }

             for(auto [r, id]: Query[i]){
                 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);
             }
         }

         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:196:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  196 | main()
      | ^~~~
election.cpp: In function 'int main()':
election.cpp:200:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:201:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12120 KB Output is correct
2 Correct 7 ms 12120 KB Output is correct
3 Correct 6 ms 12124 KB Output is correct
4 Correct 6 ms 12220 KB Output is correct
5 Correct 6 ms 12124 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12120 KB Output is correct
2 Correct 7 ms 12120 KB Output is correct
3 Correct 6 ms 12124 KB Output is correct
4 Correct 6 ms 12220 KB Output is correct
5 Correct 6 ms 12124 KB Output is correct
6 Correct 66 ms 33360 KB Output is correct
7 Correct 61 ms 33356 KB Output is correct
8 Correct 77 ms 32968 KB Output is correct
9 Correct 61 ms 33100 KB Output is correct
10 Correct 75 ms 33100 KB Output is correct
11 Correct 72 ms 33628 KB Output is correct
12 Correct 86 ms 33616 KB Output is correct
13 Correct 69 ms 33748 KB Output is correct
14 Correct 70 ms 33356 KB Output is correct
15 Correct 76 ms 33360 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12120 KB Output is correct
2 Correct 7 ms 12120 KB Output is correct
3 Correct 6 ms 12124 KB Output is correct
4 Correct 6 ms 12220 KB Output is correct
5 Correct 6 ms 12124 KB Output is correct
6 Correct 66 ms 33360 KB Output is correct
7 Correct 61 ms 33356 KB Output is correct
8 Correct 77 ms 32968 KB Output is correct
9 Correct 61 ms 33100 KB Output is correct
10 Correct 75 ms 33100 KB Output is correct
11 Correct 72 ms 33628 KB Output is correct
12 Correct 86 ms 33616 KB Output is correct
13 Correct 69 ms 33748 KB Output is correct
14 Correct 70 ms 33356 KB Output is correct
15 Correct 76 ms 33360 KB Output is correct
16 Correct 565 ms 63212 KB Output is correct
17 Correct 455 ms 62612 KB Output is correct
18 Correct 498 ms 61508 KB Output is correct
19 Correct 517 ms 62520 KB Output is correct
20 Correct 548 ms 62716 KB Output is correct
21 Correct 609 ms 65516 KB Output is correct
22 Correct 599 ms 64500 KB Output is correct
23 Correct 571 ms 64244 KB Output is correct
24 Correct 559 ms 65008 KB Output is correct
25 Correct 569 ms 63828 KB Output is correct