oj.uz

답안 #314664

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
314664 2020-10-20T16:03:03 Z apostoldaniel854 Election (BOI18_election) C++14
0 / 100
 12 ms 12288 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, 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;
}

Compilation message

election.cpp:7:42: warning: missing terminating " character
    7 | #define dbg(x) cerr << #x << " " << x << "\n
      |                                          ^

Subtask #1
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 12288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 12288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 12288 KB Output isn't correct
2 Halted 0 ms 0 KB -