oj.uz

답안 #1042865

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042865 2024-08-03T13:26:49 Z Requiem Election (BOI18_election) C++17
82 / 100
 98 ms 22992 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 = 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, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7520 KB Output is correct
2 Correct 8 ms 7516 KB Output is correct
3 Correct 6 ms 7516 KB Output is correct
4 Correct 5 ms 7516 KB Output is correct
5 Correct 4 ms 7516 KB Output is correct

Subtask #2
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7520 KB Output is correct
2 Correct 8 ms 7516 KB Output is correct
3 Correct 6 ms 7516 KB Output is correct
4 Correct 5 ms 7516 KB Output is correct
5 Correct 4 ms 7516 KB Output is correct
6 Correct 98 ms 22600 KB Output is correct
7 Correct 61 ms 22352 KB Output is correct
8 Correct 64 ms 22220 KB Output is correct
9 Correct 66 ms 22500 KB Output is correct
10 Correct 64 ms 22332 KB Output is correct
11 Correct 63 ms 22836 KB Output is correct
12 Correct 62 ms 22608 KB Output is correct
13 Correct 65 ms 22992 KB Output is correct
14 Correct 60 ms 22756 KB Output is correct
15 Correct 64 ms 22620 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7520 KB Output is correct
2 Correct 8 ms 7516 KB Output is correct
3 Correct 6 ms 7516 KB Output is correct
4 Correct 5 ms 7516 KB Output is correct
5 Correct 4 ms 7516 KB Output is correct
6 Correct 98 ms 22600 KB Output is correct
7 Correct 61 ms 22352 KB Output is correct
8 Correct 64 ms 22220 KB Output is correct
9 Correct 66 ms 22500 KB Output is correct
10 Correct 64 ms 22332 KB Output is correct
11 Correct 63 ms 22836 KB Output is correct
12 Correct 62 ms 22608 KB Output is correct
13 Correct 65 ms 22992 KB Output is correct
14 Correct 60 ms 22756 KB Output is correct
15 Correct 64 ms 22620 KB Output is correct
16 Runtime error 10 ms 16900 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -