제출 #1283475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283475		quangminh412	Election (BOI18_election)	C++17	100 / 100	465 ms	36496 KiB

election

/*
  Ben Watson

  Quang Minh MasterDDDDD
*/

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

// main program
const int maxn = 5e5 + 1;

struct Node
{
    int pre, suff, sum, finals;

    Node() : finals(-1) {};
    Node(int val)
    {
        pre = suff = finals = max(0, val);
        sum = val;
    }

    Node operator + (const Node& other)
    {
        Node res;
        if (other.finals == -1) return (*this);
        if (finals == -1) return other;
        res.sum = sum + other.sum;
        res.pre = max(pre, sum + other.pre);
        res.suff = max(other.suff, other.sum + suff);
        res.finals = max({pre + other.suff, finals + other.sum, sum + other.finals});
        return res;
    }
};

struct SegmentTree
{
    vector<Node> st;
    int n;

    SegmentTree(int n, int *arr) : n(n)
    {
        st.resize(4 * n + 1);
        build(1, 1, n, arr);
    }

    void build(int head, int l, int r, int *arr)
    {
        if (l == r)
        {
            st[head] = Node(arr[l]);
            return;
        }
        int mid = l + r >> 1;
        build(head << 1, l, mid, arr);
        build(head << 1 | 1, mid + 1, r, arr);
        st[head] = st[head << 1] + st[head << 1 | 1];
    }

    Node query(int head, int l, int r, int u, int v)
    {
        if (l > v || r < u) return Node();
        if (u <= l && r <= v) return st[head];
        int mid = l + r >> 1;
        return query(head << 1, l, mid, u, v) + query(head << 1 | 1, mid + 1, r, u, v);
    }
    int query(int u, int v) { Node res = query(1, 1, n, u, v); return res.finals; }
};

int a[maxn];
int n, q;

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        char c; cin >> c;
        a[i] = (c == 'T' ? 1 : -1);
    }

    SegmentTree st(n, a);

    cin >> q;
    while (q--)
    {
        int l, r; cin >> l >> r;

        cout << st.query(l, r) << '\n';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

election.cpp: In function 'int main()':
election.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18