oj.uz

Submission #825527

# Submission time Handle Problem Language Result Execution time Memory
825527 2023-08-15T01:17:29 Z boyliguanhan Election (BOI18_election) C++17
100 / 100
 681 ms 179968 KB 
#include<bits/stdc++.h>
using namespace std;
struct Data {
    int l=0,r=0,s=0,a=0;
    Data():l(0){}
    Data(bool b) : l(b), r(b), s(b?1:-1), a(b){}
    Data(Data a, Data b) : l(max(a.l, a.s+b.l)), r(max(b.r,b.s+a.r)), s(a.s+b.s), a(max(max(a.a+b.s, b.a+a.s), a.l+b.r)){}
};
vector<vector<Data>> tb(500100, vector<Data>(20));
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    string str;
    cin >> n >> str >> q;
    for(int i = 1; i <= n; i++) {
        tb[i][0] = Data(str[i-1]=='T');
    }
    for(int j = 1; j < 20; j++)
        for(int i = 1; i < n-(1<<j)+2; i++)
            tb[i][j] = Data(tb[i][j-1], tb[i+(1<<j-1)][j-1]);
    while(q--){
        Data d;
        int a, b;
        cin >> a >> b;
        for(int i = 20;i--;)
            if(a+(1<<i)-2<b)
                d = Data(d,tb[a][i]), a+=(1<<i);
        cout << d.a << '\n';
    }
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:21:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   21 |             tb[i][j] = Data(tb[i][j-1], tb[i+(1<<j-1)][j-1]);
      |                                                  ~^~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 176396 KB Output is correct
2 Correct 80 ms 176360 KB Output is correct
3 Correct 90 ms 176452 KB Output is correct
4 Correct 86 ms 176472 KB Output is correct
5 Correct 82 ms 176424 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 176396 KB Output is correct
2 Correct 80 ms 176360 KB Output is correct
3 Correct 90 ms 176452 KB Output is correct
4 Correct 86 ms 176472 KB Output is correct
5 Correct 82 ms 176424 KB Output is correct
6 Correct 123 ms 176908 KB Output is correct
7 Correct 127 ms 176936 KB Output is correct
8 Correct 113 ms 176864 KB Output is correct
9 Correct 115 ms 176800 KB Output is correct
10 Correct 123 ms 176680 KB Output is correct
11 Correct 119 ms 176972 KB Output is correct
12 Correct 118 ms 176952 KB Output is correct
13 Correct 126 ms 176912 KB Output is correct
14 Correct 150 ms 176916 KB Output is correct
15 Correct 120 ms 176852 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 176396 KB Output is correct
2 Correct 80 ms 176360 KB Output is correct
3 Correct 90 ms 176452 KB Output is correct
4 Correct 86 ms 176472 KB Output is correct
5 Correct 82 ms 176424 KB Output is correct
6 Correct 123 ms 176908 KB Output is correct
7 Correct 127 ms 176936 KB Output is correct
8 Correct 113 ms 176864 KB Output is correct
9 Correct 115 ms 176800 KB Output is correct
10 Correct 123 ms 176680 KB Output is correct
11 Correct 119 ms 176972 KB Output is correct
12 Correct 118 ms 176952 KB Output is correct
13 Correct 126 ms 176912 KB Output is correct
14 Correct 150 ms 176916 KB Output is correct
15 Correct 120 ms 176852 KB Output is correct
16 Correct 610 ms 178916 KB Output is correct
17 Correct 590 ms 179012 KB Output is correct
18 Correct 675 ms 178980 KB Output is correct
19 Correct 510 ms 178564 KB Output is correct
20 Correct 645 ms 178024 KB Output is correct
21 Correct 633 ms 179804 KB Output is correct
22 Correct 630 ms 179808 KB Output is correct
23 Correct 675 ms 179968 KB Output is correct
24 Correct 681 ms 179608 KB Output is correct
25 Correct 669 ms 179148 KB Output is correct