oj.uz

Submission #376996

# Submission time Handle Problem Language Result Execution time Memory
376996 2021-03-12T16:07:31 Z ntabc05101 Election (BOI18_election) C++14
100 / 100
 909 ms 36456 KB 
#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

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.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 80 ms 7916 KB Output is correct
7 Correct 67 ms 7916 KB Output is correct
8 Correct 74 ms 7916 KB Output is correct
9 Correct 70 ms 7916 KB Output is correct
10 Correct 86 ms 7916 KB Output is correct
11 Correct 86 ms 8044 KB Output is correct
12 Correct 78 ms 8032 KB Output is correct
13 Correct 79 ms 8044 KB Output is correct
14 Correct 89 ms 8044 KB Output is correct
15 Correct 79 ms 7916 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 80 ms 7916 KB Output is correct
7 Correct 67 ms 7916 KB Output is correct
8 Correct 74 ms 7916 KB Output is correct
9 Correct 70 ms 7916 KB Output is correct
10 Correct 86 ms 7916 KB Output is correct
11 Correct 86 ms 8044 KB Output is correct
12 Correct 78 ms 8032 KB Output is correct
13 Correct 79 ms 8044 KB Output is correct
14 Correct 89 ms 8044 KB Output is correct
15 Correct 79 ms 7916 KB Output is correct
16 Correct 884 ms 35452 KB Output is correct
17 Correct 738 ms 34892 KB Output is correct
18 Correct 836 ms 35336 KB Output is correct
19 Correct 678 ms 34812 KB Output is correct
20 Correct 882 ms 34308 KB Output is correct
21 Correct 893 ms 36220 KB Output is correct
22 Correct 883 ms 36092 KB Output is correct
23 Correct 909 ms 36456 KB Output is correct
24 Correct 897 ms 36064 KB Output is correct
25 Correct 878 ms 35452 KB Output is correct