oj.uz

Submission #853104

# Submission time Handle Problem Language Result Execution time Memory
853104 2023-09-23T12:25:50 Z faruk Election (BOI18_election) C++17
82 / 100
 1178 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;

    int prev_sum, first_m1_idx, first_0_idx;
    seggy seg(n);
    vector<int> out(q);

    for (auto &[query, idx] : queries) {
        if (query.first < l) {
            for (l--; l >= query.first; l--) {
                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;
                    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();
                prev_sum = l == 0 ? 0 : arr[l - 1];
                if (a[l] == 1)
                {
                    bal--;
                    if (idxs[n + prev_sum].empty())
                        continue;
                    ans1++;
                    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 14 ms 3160 KB Output is correct
2 Correct 14 ms 3160 KB Output is correct
3 Correct 12 ms 3160 KB Output is correct
4 Correct 10 ms 3164 KB Output is correct
5 Correct 12 ms 3256 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3160 KB Output is correct
2 Correct 14 ms 3160 KB Output is correct
3 Correct 12 ms 3160 KB Output is correct
4 Correct 10 ms 3164 KB Output is correct
5 Correct 12 ms 3256 KB Output is correct
6 Correct 1178 ms 99020 KB Output is correct
7 Correct 726 ms 98832 KB Output is correct
8 Correct 990 ms 98564 KB Output is correct
9 Correct 892 ms 98812 KB Output is correct
10 Correct 1166 ms 98484 KB Output is correct
11 Correct 987 ms 98732 KB Output is correct
12 Correct 1045 ms 98740 KB Output is correct
13 Correct 784 ms 98736 KB Output is correct
14 Correct 1040 ms 98732 KB Output is correct
15 Correct 1085 ms 98732 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3160 KB Output is correct
2 Correct 14 ms 3160 KB Output is correct
3 Correct 12 ms 3160 KB Output is correct
4 Correct 10 ms 3164 KB Output is correct
5 Correct 12 ms 3256 KB Output is correct
6 Correct 1178 ms 99020 KB Output is correct
7 Correct 726 ms 98832 KB Output is correct
8 Correct 990 ms 98564 KB Output is correct
9 Correct 892 ms 98812 KB Output is correct
10 Correct 1166 ms 98484 KB Output is correct
11 Correct 987 ms 98732 KB Output is correct
12 Correct 1045 ms 98740 KB Output is correct
13 Correct 784 ms 98736 KB Output is correct
14 Correct 1040 ms 98732 KB Output is correct
15 Correct 1085 ms 98732 KB Output is correct
16 Runtime error 114 ms 262144 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -