oj.uz

답안 #853094

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
853094 2023-09-23T12:16:41 Z faruk Election (BOI18_election) C++17
82 / 100
 1267 ms 262144 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define all(a) a.begin(), a.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

struct node {
    int sum, min_val;
};
void merge_node(node &t, node &a, node &b) {t.sum = a.sum + b.sum, t.min_val = min(b.min_val, a.min_val + b.sum);}

struct seggy{
    vector<node> t; int n;
    seggy(int N) {
        n = pow(2, ceil(log(N)/log(2))); t.resize(2*n, {0, 0});

    }
    int get() {return t[1].min_val;}
    void upd(int idx, int n_val) {
        for (idx += n, t[idx] = {n_val, min(0, n_val)}, idx /= 2; idx > 0; idx /= 2)
            merge_node(t[idx], t[idx*2], t[idx*2+1]);
    }
};

const int K = 500;

bool cmp(pair<pii, int> a, pair<pii, int> b) {
    if (a.first.first / K == b.first.first / K)
        return a.first.second < b.first.second;
    return a.first.first / K < b.first.first / K;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    string s;
    cin >>s;
    vector<int> arr(n);
    vector<int> a(n);
    vector<deque<int> > idxs(n*3+1);
    for (int i = 0; i < n; i++)
    {
        arr[i] = s[i] == 'T' ? -1 : 1;
        a[i] = arr[i];
        if (i != 0)
            arr[i] += arr[i - 1];
    }

    int q;
    cin >> q;
    vector<pair<pii, int>> queries;
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        queries.push_back({{l - 1, r - 1}, i});
    }
    sort(all(queries), cmp);
    int l = 0, r = -1, ans1 = 0, bal = 0;
    seggy seg(n);
    vector<int> out(q);

    for (auto &[query, idx] : queries) {
        if (query.first < l) {
            for (l--; l >= query.first; l--) {
                int prev_sum = arr[l];
                idxs[arr[l]+n].push_front(l);
                if (a[l] == -1) {
                    ans1++;
                } else {
                    bal++;
                    seg.upd(l, 1);
                    if (n + prev_sum - 1 < 0 || idxs[n + prev_sum - 1].empty())
                        continue;
                    int first_m1_idx = idxs[n + prev_sum - 1].front();
                    seg.upd(first_m1_idx, -1);
                    bal--;
                    ans1--;
                }
            }
            l++;
        }

        if (query.second > r) {
            for (r++; r <= query.second; r++) {
                if (a[r] == 1) {
                    seg.upd(r, 1), bal++;
                }
                else {
                    if (bal == 0)
                        ans1++;
                    else
                        seg.upd(r, -1), bal--;
                }
                idxs[arr[r] + n].push_back(r);
            }
            r--;
        }

        if (query.first > l) {
            for (;l < query.first; l++) {
                if (seg.t[seg.n+l].sum != 0)
                    seg.upd(l, 0);
                idxs[arr[l]+n].pop_front();
                int prev_sum = l == 0 ? 0 : arr[l - 1];
                if (a[l] == 1)
                {
                    bal--;
                    if (idxs[n + prev_sum].empty())
                        continue;
                    ans1++;
                    int first_0_idx = idxs[n + prev_sum].front();
                    seg.upd(first_0_idx, 0);
                    bal++;
                } else
                    ans1--;
            }
        }

        if (query.second < r) {
            for (; r > query.second; r--) {
                idxs[arr[r] + n].pop_back();
                if (a[r] == 1) {
                    seg.upd(r, 0);
                    bal--;
                } else {
                    if (seg.t[r+seg.n].sum == 0)
                        ans1--;
                    else
                        seg.upd(r, 0), bal++;
                }
            }
        }
        out[idx] = -seg.get() + ans1;
    }

    for (int a : out)
        cout <<a << "\n";
    cout << "\n";
}

Subtask #1
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 4440 KB Output is correct
2 Correct 13 ms 4444 KB Output is correct
3 Correct 15 ms 4608 KB Output is correct
4 Correct 11 ms 4440 KB Output is correct
5 Correct 12 ms 4440 KB Output is correct

Subtask #2
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 4440 KB Output is correct
2 Correct 13 ms 4444 KB Output is correct
3 Correct 15 ms 4608 KB Output is correct
4 Correct 11 ms 4440 KB Output is correct
5 Correct 12 ms 4440 KB Output is correct
6 Correct 1267 ms 145768 KB Output is correct
7 Correct 740 ms 146064 KB Output is correct
8 Correct 1046 ms 145864 KB Output is correct
9 Correct 950 ms 145796 KB Output is correct
10 Correct 1240 ms 145596 KB Output is correct
11 Correct 1024 ms 145860 KB Output is correct
12 Correct 1080 ms 145852 KB Output is correct
13 Correct 817 ms 145860 KB Output is correct
14 Correct 1068 ms 145860 KB Output is correct
15 Correct 1131 ms 145860 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 4440 KB Output is correct
2 Correct 13 ms 4444 KB Output is correct
3 Correct 15 ms 4608 KB Output is correct
4 Correct 11 ms 4440 KB Output is correct
5 Correct 12 ms 4440 KB Output is correct
6 Correct 1267 ms 145768 KB Output is correct
7 Correct 740 ms 146064 KB Output is correct
8 Correct 1046 ms 145864 KB Output is correct
9 Correct 950 ms 145796 KB Output is correct
10 Correct 1240 ms 145596 KB Output is correct
11 Correct 1024 ms 145860 KB Output is correct
12 Correct 1080 ms 145852 KB Output is correct
13 Correct 817 ms 145860 KB Output is correct
14 Correct 1068 ms 145860 KB Output is correct
15 Correct 1131 ms 145860 KB Output is correct
16 Runtime error 111 ms 262144 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -