Submission #376996

#	Time	Username	Problem	Language	Result	Execution time	Memory
376996		ntabc05101	Election (BOI18_election)	C++14	100 / 100	909 ms	36456 KiB

election

#ifndef LOCAL
#define NDEBUG 1
#endif // LOCAL
#include<bits/stdc++.h>

const int max_n=500000;

int n;
std::string str;

struct Node {
        int max_l, max_r, tot, ans;

        Node operator + (Node const& other) {
                Node ret;
                ret.max_l=std::max(max_l, tot+other.max_l);
                ret.max_r=std::max(max_r+other.tot, other.max_r);
                ret.tot=tot+other.tot;
                ret.ans=std::max(std::max(ans+other.tot, tot+other.ans), max_l+other.max_r);

                return ret;
        }
};

Node nodes[max_n<<2];
int L[max_n<<2], H[max_n<<2];

void build(int node, int low, int high) {
        L[node]=low;
        H[node]=high;
        if (low==high) {
                if (str[high-1]=='C') {
                        nodes[node]={0, 0, -1, 0};
                }
                else {
                        nodes[node]={1, 1, 1, 1};
                }
                return ;
        }

        int mid=low+high>>1;
        build(node<<1, low, mid);
        build(node<<1|1, mid+1, high);

        nodes[node]=nodes[node<<1]+nodes[node<<1|1];
}

Node get(int node, int leftq, int rightq) {
        if (L[node]>rightq or H[node]<leftq) {
                return {0, 0, 0, 0};
        }

        if (L[node]>=leftq and H[node]<=rightq) {
                return nodes[node];
        }

        return get(node<<1, leftq, rightq)+get(node<<1|1, leftq, rightq);
}

int main() {
        std::ios_base::sync_with_stdio(0); std::cin.tie(0);

        int q;
        std::cin>>n>>str>>q;
        build(1, 1, n);

        while (q--) {
                int x, y; std::cin>>x>>y;
                std::cout<<get(1, x, y).ans<<"\n";
        }

        return 0;
}

Compilation message (stderr)

election.cpp: In function 'void build(int, int, int)':
election.cpp:41:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int mid=low+high>>1;
      |                 ~~~^~~~~

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