oj.uz

답안 #314665

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
314665 2020-10-20T16:07:58 Z apostoldaniel854 Election (BOI18_election) C++14
100 / 100
 1458 ms 54692 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

const int N = 5e5;
struct SegTree {
    ///
    struct Node {
        int sum;
        int mnSuf;
    };
    vector <Node> seg;
    int n;
    SegTree (int n) {
        this-> n = n;
        seg.resize (1 + 4 * n);
    }
    Node join (Node lNode, Node rNode) {
        return {lNode.sum + rNode.sum, min (rNode.mnSuf, lNode.mnSuf + rNode.sum)};
    }
    void updatePos (int node, int lb, int rb, int pos, int val) {
        if (lb == rb) {
            seg[node] = {val, min (val, 0)};
            return;
        }
        int mid = (lb + rb) / 2;
        if (pos <= mid)
            updatePos (node * 2, lb, mid, pos, val);
        else
            updatePos (node * 2 + 1, mid + 1, rb, pos, val);
        seg[node] = join (seg[node * 2], seg[node * 2 + 1]);
    }
    Node queryRange (int node, int lb, int rb, int qL, int qR) {
        if (qL <= lb && rb <= qR)
            return seg[node];
        int mid = (lb + rb) / 2;
        Node ans = {0, 0};
        if (qL <= mid)
            ans = join (ans, queryRange (node * 2, lb, mid, qL, qR));
        if (qR >= mid + 1)
            ans = join (ans, queryRange (node * 2 + 1, mid + 1, rb, qL, qR));
        return ans;
    }
};
vector <pair <int, int>> qry[1 + N];
int val[1 + N];

int main () {
    int n;
    string votes;
    cin >> n >> votes;
    for (int i = 0; i < n; i++)
        val[i + 1] = votes[i] == 'C' ? 1 : -1;
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        qry[l].pb ({r, i});
    }
    SegTree seg (n);
    vector <int> stk;
    for (int i = 1; i <= n; i++)
        seg.updatePos (1, 1, n, i, val[i]);
    vector <int> sol (q);
    for (int i = n; i > 0; i--) {
        if (val[i] == 1) {
            if (stk.size ()) {
                seg.updatePos (1, 1, n, stk.back (), -1);
                stk.pop_back ();
            }
        }
        else {
            seg.updatePos (1, 1, n, i, 0);
            stk.push_back (i);
        }
        for (pair <int, int> it : qry[i]) {
            int l = i;
            int r = it.first;
            int index = it.second;
            sol[index] = - seg.queryRange (1, 1, n, l, r).mnSuf + (upper_bound (stk.rbegin (), stk.rend (), r) - stk.rbegin ());
        }
    }
    for (int x : sol)
        cout << x << "\n";
    cout << "\n";
    return 0;
}

Subtask #1
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 13 ms 12272 KB Output is correct
3 Correct 12 ms 12160 KB Output is correct
4 Correct 13 ms 12416 KB Output is correct
5 Correct 12 ms 12288 KB Output is correct

Subtask #2
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 13 ms 12272 KB Output is correct
3 Correct 12 ms 12160 KB Output is correct
4 Correct 13 ms 12416 KB Output is correct
5 Correct 12 ms 12288 KB Output is correct
6 Correct 165 ms 17784 KB Output is correct
7 Correct 144 ms 17144 KB Output is correct
8 Correct 154 ms 17272 KB Output is correct
9 Correct 163 ms 17444 KB Output is correct
10 Correct 159 ms 17400 KB Output is correct
11 Correct 171 ms 17784 KB Output is correct
12 Correct 163 ms 17784 KB Output is correct
13 Correct 169 ms 17912 KB Output is correct
14 Correct 161 ms 17656 KB Output is correct
15 Correct 156 ms 17656 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 13 ms 12272 KB Output is correct
3 Correct 12 ms 12160 KB Output is correct
4 Correct 13 ms 12416 KB Output is correct
5 Correct 12 ms 12288 KB Output is correct
6 Correct 165 ms 17784 KB Output is correct
7 Correct 144 ms 17144 KB Output is correct
8 Correct 154 ms 17272 KB Output is correct
9 Correct 163 ms 17444 KB Output is correct
10 Correct 159 ms 17400 KB Output is correct
11 Correct 171 ms 17784 KB Output is correct
12 Correct 163 ms 17784 KB Output is correct
13 Correct 169 ms 17912 KB Output is correct
14 Correct 161 ms 17656 KB Output is correct
15 Correct 156 ms 17656 KB Output is correct
16 Correct 1390 ms 52528 KB Output is correct
17 Correct 1191 ms 48468 KB Output is correct
18 Correct 1301 ms 49564 KB Output is correct
19 Correct 1240 ms 51116 KB Output is correct
20 Correct 1357 ms 51632 KB Output is correct
21 Correct 1458 ms 54320 KB Output is correct
22 Correct 1406 ms 53424 KB Output is correct
23 Correct 1424 ms 54692 KB Output is correct
24 Correct 1375 ms 53820 KB Output is correct
25 Correct 1349 ms 52712 KB Output is correct