oj.uz

Submission #853091

# Submission time Handle Problem Language Result Execution time Memory
853091 2023-09-23T12:15:36 Z faruk Election (BOI18_election) C++17
82 / 100
 1393 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 = 300;

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

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4696 KB Output is correct
2 Correct 11 ms 4444 KB Output is correct
3 Correct 11 ms 4440 KB Output is correct
4 Correct 8 ms 4444 KB Output is correct
5 Correct 9 ms 4444 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4696 KB Output is correct
2 Correct 11 ms 4444 KB Output is correct
3 Correct 11 ms 4440 KB Output is correct
4 Correct 8 ms 4444 KB Output is correct
5 Correct 9 ms 4444 KB Output is correct
6 Correct 1393 ms 146532 KB Output is correct
7 Correct 542 ms 146944 KB Output is correct
8 Correct 1304 ms 146616 KB Output is correct
9 Correct 1256 ms 146880 KB Output is correct
10 Correct 1380 ms 146548 KB Output is correct
11 Correct 1143 ms 146808 KB Output is correct
12 Correct 1221 ms 146808 KB Output is correct
13 Correct 947 ms 146812 KB Output is correct
14 Correct 1229 ms 146792 KB Output is correct
15 Correct 1304 ms 146816 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4696 KB Output is correct
2 Correct 11 ms 4444 KB Output is correct
3 Correct 11 ms 4440 KB Output is correct
4 Correct 8 ms 4444 KB Output is correct
5 Correct 9 ms 4444 KB Output is correct
6 Correct 1393 ms 146532 KB Output is correct
7 Correct 542 ms 146944 KB Output is correct
8 Correct 1304 ms 146616 KB Output is correct
9 Correct 1256 ms 146880 KB Output is correct
10 Correct 1380 ms 146548 KB Output is correct
11 Correct 1143 ms 146808 KB Output is correct
12 Correct 1221 ms 146808 KB Output is correct
13 Correct 947 ms 146812 KB Output is correct
14 Correct 1229 ms 146792 KB Output is correct
15 Correct 1304 ms 146816 KB Output is correct
16 Runtime error 113 ms 262144 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -