oj.uz

Submission #853101

# Submission time Handle Problem Language Result Execution time Memory
853101 2023-09-23T12:22:24 Z faruk Election (BOI18_election) C++17
82 / 100
 1182 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*2+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

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3416 KB Output is correct
2 Correct 12 ms 3416 KB Output is correct
3 Correct 12 ms 3164 KB Output is correct
4 Correct 10 ms 3160 KB Output is correct
5 Correct 12 ms 3160 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3416 KB Output is correct
2 Correct 12 ms 3416 KB Output is correct
3 Correct 12 ms 3164 KB Output is correct
4 Correct 10 ms 3160 KB Output is correct
5 Correct 12 ms 3160 KB Output is correct
6 Correct 1170 ms 98764 KB Output is correct
7 Correct 705 ms 98940 KB Output is correct
8 Correct 993 ms 98564 KB Output is correct
9 Correct 892 ms 98768 KB Output is correct
10 Correct 1182 ms 98480 KB Output is correct
11 Correct 1000 ms 98736 KB Output is correct
12 Correct 1029 ms 98732 KB Output is correct
13 Correct 794 ms 98732 KB Output is correct
14 Correct 1031 ms 98748 KB Output is correct
15 Correct 1104 ms 98792 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3416 KB Output is correct
2 Correct 12 ms 3416 KB Output is correct
3 Correct 12 ms 3164 KB Output is correct
4 Correct 10 ms 3160 KB Output is correct
5 Correct 12 ms 3160 KB Output is correct
6 Correct 1170 ms 98764 KB Output is correct
7 Correct 705 ms 98940 KB Output is correct
8 Correct 993 ms 98564 KB Output is correct
9 Correct 892 ms 98768 KB Output is correct
10 Correct 1182 ms 98480 KB Output is correct
11 Correct 1000 ms 98736 KB Output is correct
12 Correct 1029 ms 98732 KB Output is correct
13 Correct 794 ms 98732 KB Output is correct
14 Correct 1031 ms 98748 KB Output is correct
15 Correct 1104 ms 98792 KB Output is correct
16 Runtime error 118 ms 262144 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -