oj.uz

Submission #572233

# Submission time Handle Problem Language Result Execution time Memory
572233 2022-06-04T03:04:20 Z hoanghq2004 Election (BOI18_election) C++14
100 / 100
 1103 ms 48172 KB 
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 5e5 + 10;

int n, q;
int p[N], s[N], L[N], R[N];
char c[N];
int flag[N];

struct SegmentTree {
    int st[N * 4];
    int lazy[N * 4];
    void push(int id, int delta) {
        st[id] += delta;
        lazy[id] += delta;
    }
    void add(int id, int L, int R, int u, int v, int delta) {
        if (u > R || L > v) return;
        if (u <= L && R <= v) {
            push(id, delta);
            return;
        }
        push(id * 2, lazy[id]);
        push(id * 2 + 1, lazy[id]);
        lazy[id] = 0;
        int mid = L + R >> 1;
        add(id * 2, L, mid, u, v, delta);
        add(id * 2 + 1, mid + 1, R, u, v, delta);
        st[id] = min(st[id * 2], st[id * 2 + 1]);
    }
    int get(int id, int L, int R, int u, int v) {
        if (u > R || L > v) return 1e9;
        if (u <= L && R <= v) return st[id];
        push(id * 2, lazy[id]);
        push(id * 2 + 1, lazy[id]);
        lazy[id] = 0;
        int mid = L + R >> 1;
        return min(get(id * 2, L, mid, u, v), get(id * 2 + 1, mid + 1, R, u, v));
    }
} F, B;

int ans[N];

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> c[i];
    for (int i = 1; i <= n; ++i) p[i] = p[i - 1] + (c[i] == 'C' ? 1 : -1);
    vector <int> stk;
    for (int i = n; i >= 0; --i) {
        while (stk.size() && p[i] <= p[stk.back()]) {
            L[stk.back()] = i;
            stk.pop_back();
        }
        stk.push_back(i);
    }
    while (stk.size()) {
        L[stk.back()] = -1;
        stk.pop_back();
    }
    for (int i = 1; i <= n; ++i) F.add(1, 1, n, i, n, (c[i] == 'C' ? 1 : -1));
    for (int i = 1; i <= n; ++i) B.add(1, 1, n, 1, i, (c[i] == 'C' ? 1 : -1));
    cin >> q;
    vector <tuple <int, int, int>> work;
    for (int i = 0; i < q; ++i) {
        int u, v;
        cin >> u >> v;
        ans[i] = - min(0, F.get(1, 1, n, u, v) - p[u - 1]);
        work.push_back({u, v, i});
    }
    sort(work.begin(), work.end());
    vector <pair <int, int>> s;
    for (int i = 1; i <= n; ++i) s.push_back({L[i] + 1, i});
    sort(s.begin(), s.end());
    int j = 0;
    for (auto [u, v, i]: work) {
        while (j < s.size() && s[j].first < u) {
            B.add(1, 1, n, 1, s[j].second, 1);
            ++j;
        }
        int b = (v == n ? 0 : B.get(1, 1, n, v + 1, v + 1));
        ans[i] -= min(0, B.get(1, 1, n, u, v) - b);
    }
    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
}

Compilation message

election.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
election.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
election.cpp: In member function 'void SegmentTree::add(int, int, int, int, int, int)':
election.cpp:36:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int mid = L + R >> 1;
      |                   ~~^~~
election.cpp: In member function 'int SegmentTree::get(int, int, int, int, int)':
election.cpp:47:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int mid = L + R >> 1;
      |                   ~~^~~
election.cpp: In function 'int main()':
election.cpp:86:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |     for (auto [u, v, i]: work) {
      |               ^
election.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         while (j < s.size() && s[j].first < u) {
      |                ~~^~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 476 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 524 KB Output is correct
4 Correct 3 ms 472 KB Output is correct
5 Correct 3 ms 468 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 476 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 524 KB Output is correct
4 Correct 3 ms 472 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 130 ms 8996 KB Output is correct
7 Correct 120 ms 8920 KB Output is correct
8 Correct 107 ms 8852 KB Output is correct
9 Correct 104 ms 8860 KB Output is correct
10 Correct 111 ms 8772 KB Output is correct
11 Correct 120 ms 9080 KB Output is correct
12 Correct 109 ms 9052 KB Output is correct
13 Correct 128 ms 9148 KB Output is correct
14 Correct 122 ms 9072 KB Output is correct
15 Correct 123 ms 8980 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 476 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 524 KB Output is correct
4 Correct 3 ms 472 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 130 ms 8996 KB Output is correct
7 Correct 120 ms 8920 KB Output is correct
8 Correct 107 ms 8852 KB Output is correct
9 Correct 104 ms 8860 KB Output is correct
10 Correct 111 ms 8772 KB Output is correct
11 Correct 120 ms 9080 KB Output is correct
12 Correct 109 ms 9052 KB Output is correct
13 Correct 128 ms 9148 KB Output is correct
14 Correct 122 ms 9072 KB Output is correct
15 Correct 123 ms 8980 KB Output is correct
16 Correct 1051 ms 46668 KB Output is correct
17 Correct 780 ms 46296 KB Output is correct
18 Correct 990 ms 46596 KB Output is correct
19 Correct 902 ms 46032 KB Output is correct
20 Correct 1038 ms 45756 KB Output is correct
21 Correct 1058 ms 47924 KB Output is correct
22 Correct 1103 ms 47520 KB Output is correct
23 Correct 995 ms 48172 KB Output is correct
24 Correct 961 ms 47596 KB Output is correct
25 Correct 961 ms 46960 KB Output is correct