oj.uz

Submission #414212

# Submission time Handle Problem Language Result Execution time Memory
414212 2021-05-30T09:15:20 Z shivensinha4 Election (BOI18_election) C++17
82 / 100
 3000 ms 51856 KB 
#include <bits/stdc++.h>
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
//#define endl '\n'

struct Node {
    int pref = 0, sum = 0;
};

class SegmentTree {
public:
//private:
    vector<Node> tree; int n;
    Node bound = {0, 0};

    static Node merge(Node a, Node b) {
        Node ans;
        ans.sum = a.sum + b.sum;
        ans.pref = max(a.pref, a.sum + b.pref);
        return ans;
    }

    void update(int i, int val, int l, int r, int p) {
        if (l > i or r < i) return;
        if (l == r) {
            tree[p] = {val, val};
            return;
        }

        int mid = (l + r) / 2;
        int c1 = 2*p+1, c2 = 2*p+2;
        update(i, val, l, mid, c1); update(i, val, mid+1, r, c2);
        tree[p] = merge(tree[c1], tree[c2]);
    }

    Node mx(int i, int j, int l, int r, int p) {
        if (l > j or r < i) return bound;
        if (l >= i and r <= j) return tree[p];

        int mid = (l + r) / 2;
        int c1 = 2*p+1, c2 = 2*p+2;
        return merge(mx(i, j, l, mid, c1), mx(i, j, mid+1, r, c2));
    }

//public:
    SegmentTree(int _n) {
        n = _n;
        tree.resize(4*n, bound);
    }

    Node mx(int i, int j) {
        return mx(i, j, 0, n-1, 0);
    }

    void update(int i, int val) {
        update(i, val, 0, n-1, 0);
    }
};


int main() {
#ifdef mlocal
    freopen("test.in", "r", stdin);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;
    vi nums(n);
    for_(i, 0, n) {
        char c; cin >> c;
        nums[i] = c == 'C' ? 1 : -1;
    }

    SegmentTree tree(n);

    int q; cin >> q;
    vector<vector<ii>> ends(n);
    for_(i, 0, q) {
        int l, r; cin >> l >> r;
        ends[l-1].push_back({r-1, i});
    }

    vi out(q);

    vi st;
    for (int i = n-1; i >= 0; i--) {
        if (nums[i] == -1) st.push_back(i);
        else {
            tree.update(i, 1);
            if (st.size()) {
                tree.update(st.back(), -1);
                st.pop_back();
            }
        }

        int ans = st.size();
        for (auto &r: ends[i]) {
//            cout << "updating " << r[1] << endl;
            Node temp = tree.mx(i, r[0]);
            out[r[1]] = temp.pref - temp.sum;
            for (auto j: st) if (j <= r[0]) out[r[1]]++;
        }

    }

    for (auto i: out) cout << i << endl;
    cout << endl;

//    cout << ans + tree.mx(0, n-1) - tree.tree[0].sum << endl;
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:102:13: warning: unused variable 'ans' [-Wunused-variable]
  102 |         int ans = st.size();
      |             ^~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 460 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 5 ms 460 KB Output is correct
4 Correct 7 ms 452 KB Output is correct
5 Correct 6 ms 460 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 460 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 5 ms 460 KB Output is correct
4 Correct 7 ms 452 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Correct 264 ms 7360 KB Output is correct
7 Correct 208 ms 6852 KB Output is correct
8 Correct 174 ms 6980 KB Output is correct
9 Correct 181 ms 7236 KB Output is correct
10 Correct 174 ms 7260 KB Output is correct
11 Correct 1309 ms 7492 KB Output is correct
12 Correct 785 ms 7432 KB Output is correct
13 Correct 2199 ms 7720 KB Output is correct
14 Correct 694 ms 7452 KB Output is correct
15 Correct 248 ms 7404 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 460 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 5 ms 460 KB Output is correct
4 Correct 7 ms 452 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Correct 264 ms 7360 KB Output is correct
7 Correct 208 ms 6852 KB Output is correct
8 Correct 174 ms 6980 KB Output is correct
9 Correct 181 ms 7236 KB Output is correct
10 Correct 174 ms 7260 KB Output is correct
11 Correct 1309 ms 7492 KB Output is correct
12 Correct 785 ms 7432 KB Output is correct
13 Correct 2199 ms 7720 KB Output is correct
14 Correct 694 ms 7452 KB Output is correct
15 Correct 248 ms 7404 KB Output is correct
16 Correct 1954 ms 51856 KB Output is correct
17 Correct 1307 ms 47752 KB Output is correct
18 Correct 1685 ms 48968 KB Output is correct
19 Correct 1963 ms 50720 KB Output is correct
20 Correct 1418 ms 50980 KB Output is correct
21 Execution timed out 3056 ms 50392 KB Time limit exceeded
22 Halted 0 ms 0 KB -