oj.uz

Submission #702343

# Submission time Handle Problem Language Result Execution time Memory
702343 2023-02-23T15:37:36 Z stevancv Election (BOI18_election) C++14
100 / 100
 852 ms 50008 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 5e5 + 2;
const int inf = 2e9;
int a[N], p[N], n;
int st[4 * N], lzy[4 * N];
void Init(int node, int l, int r) {
    if (l == r) {
        st[node] = p[l];
        return;
    }
    int mid = l + r >> 1;
    Init(2 * node, l, mid);
    Init(2 * node + 1, mid + 1, r);
    st[node] = max(st[2 * node], st[2 * node + 1]);
}
void Propagate(int node, int l, int r) {
    if (lzy[node] == 0) return;
    if (l < r) {
        lzy[2 * node] += lzy[node];
        lzy[2 * node + 1] += lzy[node];
    }
    st[node] += lzy[node];
    lzy[node] = 0;
}
void Add(int node, int l, int r, int ql, int qr, int x) {
    Propagate(node, l, r);
    if (r < ql || qr < l || ql > qr) return;
    if (ql <= l && r <= qr) {
        lzy[node] += x;
        Propagate(node, l, r);
        return;
    }
    int mid = l + r >> 1;
    Add(2 * node, l, mid, ql, qr, x);
    Add(2 * node + 1, mid + 1, r, ql, qr, x);
    st[node] = max(st[2 * node], st[2 * node + 1]);
}
int Get(int node, int l, int r, int ql, int qr) {
    Propagate(node, l, r);
    if (r < ql || qr < l) return -inf;
    if (ql <= l && r <= qr) return st[node];
    int mid = l + r >> 1;
    return max(Get(2 * node, l, mid, ql, qr), Get(2 * node + 1, mid + 1, r, ql, qr));
}
vector<int> qq[N], stk;
void Do(int x) {
    stk.push_back(x);
    Add(1, 1, n, x, n, -1);
}
void Undo() {
    if (stk.size() == 0) return;
    int x = stk.back(); stk.pop_back();
    Add(1, 1, n, x, n, 1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    string s; cin >> s;
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == 'C') a[i] = -1;
        else a[i] = 1;
        p[i] = p[i - 1] + a[i];
    }
    Init(1, 1, n);
    int q; cin >> q;
    vector<int> l(q), r(q), ans(q);
    for (int i = 0; i < q; i++) {
        cin >> l[i] >> r[i];
        qq[r[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == 'T') Do(i);
        else Undo();
        for (int j : qq[i]) {
            int o = Get(1, 1, n, l[j], r[j]);
            if (l[j] >= 2) o -= Get(1, 1, n, l[j] - 1, l[j] - 1);
            int u = (int)(lower_bound(stk.begin(), stk.end(), l[j]) - stk.begin());
            ans[j] = stk.size() - u + max(o, 0);
        }
    }
    for (int i = 0; i < q; i++) cout << ans[i] << en;
    return 0;
}

Compilation message

election.cpp: In function 'void Init(int, int, int)':
election.cpp:18:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |     int mid = l + r >> 1;
      |               ~~^~~
election.cpp: In function 'void Add(int, int, int, int, int, int)':
election.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = l + r >> 1;
      |               ~~^~~
election.cpp: In function 'int Get(int, int, int, int, int)':
election.cpp:49:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12116 KB Output is correct
2 Correct 8 ms 12216 KB Output is correct
3 Correct 11 ms 12116 KB Output is correct
4 Correct 9 ms 12244 KB Output is correct
5 Correct 8 ms 12192 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12116 KB Output is correct
2 Correct 8 ms 12216 KB Output is correct
3 Correct 11 ms 12116 KB Output is correct
4 Correct 9 ms 12244 KB Output is correct
5 Correct 8 ms 12192 KB Output is correct
6 Correct 93 ms 17976 KB Output is correct
7 Correct 83 ms 17352 KB Output is correct
8 Correct 88 ms 17584 KB Output is correct
9 Correct 82 ms 17920 KB Output is correct
10 Correct 82 ms 17780 KB Output is correct
11 Correct 95 ms 18192 KB Output is correct
12 Correct 87 ms 17992 KB Output is correct
13 Correct 91 ms 18232 KB Output is correct
14 Correct 91 ms 17944 KB Output is correct
15 Correct 81 ms 17740 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12116 KB Output is correct
2 Correct 8 ms 12216 KB Output is correct
3 Correct 11 ms 12116 KB Output is correct
4 Correct 9 ms 12244 KB Output is correct
5 Correct 8 ms 12192 KB Output is correct
6 Correct 93 ms 17976 KB Output is correct
7 Correct 83 ms 17352 KB Output is correct
8 Correct 88 ms 17584 KB Output is correct
9 Correct 82 ms 17920 KB Output is correct
10 Correct 82 ms 17780 KB Output is correct
11 Correct 95 ms 18192 KB Output is correct
12 Correct 87 ms 17992 KB Output is correct
13 Correct 91 ms 18232 KB Output is correct
14 Correct 91 ms 17944 KB Output is correct
15 Correct 81 ms 17740 KB Output is correct
16 Correct 793 ms 48272 KB Output is correct
17 Correct 627 ms 43808 KB Output is correct
18 Correct 735 ms 46232 KB Output is correct
19 Correct 670 ms 48344 KB Output is correct
20 Correct 780 ms 47392 KB Output is correct
21 Correct 852 ms 49840 KB Output is correct
22 Correct 775 ms 48864 KB Output is correct
23 Correct 817 ms 50008 KB Output is correct
24 Correct 788 ms 49180 KB Output is correct
25 Correct 741 ms 46944 KB Output is correct