Submission #774484

#	Time	Username	Problem	Language	Result	Execution time	Memory
774484		PanosPask	Election (BOI18_election)	C++14	100 / 100	448 ms	29252 KiB

election

#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 (stderr)

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 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18