oj.uz

Submission #774484

# Submission time Handle Problem Language Result Execution time Memory
774484 2023-07-05T18:40:36 Z PanosPask Election (BOI18_election) C++14
100 / 100
 448 ms 29252 KB 
#include <bits/stdc++.h>

using namespace std;

struct SegTree {
    struct Node {
        int pref;
        int suff;
        int total;
        int ans;
    };

    Node NEUTRAL = {0, 0, 0, 0};

    Node create(int v) {
        Node c;
        c.pref = c.suff = max(v, 0);
        c.total = v;
        c.ans = max(v, 0);

        return  c;
    }

    Node merge(Node a, Node b) {
        Node c;
        c.pref = max(a.pref, a.total + b.pref);
        c.suff = max(b.suff, b.total + a.suff);
        c.total = a.total + b.total;

        c.ans = max(max(a.ans + b.total, a.total + b.ans), a.pref + b.suff);
        return c;
    }

    int size;
    vector<Node> tree;

    void build(vector<int>& a, int x, int lx, int rx) {
        if (lx == rx - 1) {
            if (lx < a.size())
                tree[x] = create(a[lx]);
            else
                tree[x] = NEUTRAL;

            return;
        }

        int mid = (lx + rx) / 2;
        build(a, 2 * x + 1, lx, mid);
        build(a, 2 * x + 2, mid, rx);

        tree[x] = merge(tree[2 * x + 1], tree[2 * x + 2]);
    }

    void init(int n, vector<int>& a) {
        size = 1;
        while (size < n)
            size *= 2;

        tree.assign(2 * size, NEUTRAL);
        build(a, 0, 0, size);
    }

    Node calc(int l, int r, int x, int lx, int rx) {
        if (lx >= r || l >= rx) {
            return NEUTRAL;
        }
        else if (l <= lx && rx <= r) {
            return tree[x];
        }

        int mid = (lx + rx) / 2;
        Node c1 = calc(l, r, 2 * x + 1, lx, mid);
        Node c2 = calc(l, r, 2 * x + 2, mid, rx);

        return merge(c1, c2);
    }
    int calc(int l, int r) {
        return calc(l, r, 0, 0, size).ans;
    }
};

int n, q;
SegTree st;
vector<int> a;

int main(void)
{
    scanf("%d", &n);

    a.resize(n);

    for (int i = 0; i < n; i++) {
        char c;
        scanf(" %c", &c);
        a[i] = (c == 'T' ? 1 : -1);
    }

    scanf("%d", &q);

    st.init(n, a);
    while (q--) {
        int l, r;
        scanf("%d %d", &l, &r);
        l--;

        printf("%d\n", st.calc(l, r));
    }

    return 0;
}

Compilation message

election.cpp: In member function 'void SegTree::build(std::vector<int>&, int, int, int)':
election.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             if (lx < a.size())
      |                 ~~~^~~~~~~~~~
election.cpp: In function 'int main()':
election.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
election.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~
election.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
election.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 312 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 52 ms 5776 KB Output is correct
7 Correct 43 ms 5812 KB Output is correct
8 Correct 41 ms 5816 KB Output is correct
9 Correct 45 ms 5836 KB Output is correct
10 Correct 43 ms 5708 KB Output is correct
11 Correct 44 ms 5964 KB Output is correct
12 Correct 44 ms 5884 KB Output is correct
13 Correct 44 ms 5972 KB Output is correct
14 Correct 54 ms 5896 KB Output is correct
15 Correct 51 ms 5796 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 52 ms 5776 KB Output is correct
7 Correct 43 ms 5812 KB Output is correct
8 Correct 41 ms 5816 KB Output is correct
9 Correct 45 ms 5836 KB Output is correct
10 Correct 43 ms 5708 KB Output is correct
11 Correct 44 ms 5964 KB Output is correct
12 Correct 44 ms 5884 KB Output is correct
13 Correct 44 ms 5972 KB Output is correct
14 Correct 54 ms 5896 KB Output is correct
15 Correct 51 ms 5796 KB Output is correct
16 Correct 397 ms 28240 KB Output is correct
17 Correct 330 ms 27904 KB Output is correct
18 Correct 380 ms 28108 KB Output is correct
19 Correct 324 ms 27596 KB Output is correct
20 Correct 386 ms 27352 KB Output is correct
21 Correct 448 ms 29128 KB Output is correct
22 Correct 406 ms 29044 KB Output is correct
23 Correct 412 ms 29252 KB Output is correct
24 Correct 440 ms 28868 KB Output is correct
25 Correct 377 ms 28468 KB Output is correct