oj.uz

Submission #825526

# Submission time Handle Problem Language Result Execution time Memory
825526 2023-08-15T01:14:33 Z boyliguanhan Election (BOI18_election) C++17
100 / 100
 1541 ms 187688 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() {
    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:19:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   19 |             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 86 ms 176460 KB Output is correct
2 Correct 83 ms 176460 KB Output is correct
3 Correct 84 ms 176392 KB Output is correct
4 Correct 85 ms 176484 KB Output is correct
5 Correct 84 ms 176464 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 176460 KB Output is correct
2 Correct 83 ms 176460 KB Output is correct
3 Correct 84 ms 176392 KB Output is correct
4 Correct 85 ms 176484 KB Output is correct
5 Correct 84 ms 176464 KB Output is correct
6 Correct 222 ms 177928 KB Output is correct
7 Correct 210 ms 177728 KB Output is correct
8 Correct 208 ms 177756 KB Output is correct
9 Correct 212 ms 177764 KB Output is correct
10 Correct 229 ms 177656 KB Output is correct
11 Correct 235 ms 177884 KB Output is correct
12 Correct 217 ms 177912 KB Output is correct
13 Correct 239 ms 177868 KB Output is correct
14 Correct 215 ms 177864 KB Output is correct
15 Correct 215 ms 177868 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 176460 KB Output is correct
2 Correct 83 ms 176460 KB Output is correct
3 Correct 84 ms 176392 KB Output is correct
4 Correct 85 ms 176484 KB Output is correct
5 Correct 84 ms 176464 KB Output is correct
6 Correct 222 ms 177928 KB Output is correct
7 Correct 210 ms 177728 KB Output is correct
8 Correct 208 ms 177756 KB Output is correct
9 Correct 212 ms 177764 KB Output is correct
10 Correct 229 ms 177656 KB Output is correct
11 Correct 235 ms 177884 KB Output is correct
12 Correct 217 ms 177912 KB Output is correct
13 Correct 239 ms 177868 KB Output is correct
14 Correct 215 ms 177864 KB Output is correct
15 Correct 215 ms 177868 KB Output is correct
16 Correct 1321 ms 186736 KB Output is correct
17 Correct 1295 ms 186360 KB Output is correct
18 Correct 1264 ms 186512 KB Output is correct
19 Correct 1209 ms 186076 KB Output is correct
20 Correct 1307 ms 185808 KB Output is correct
21 Correct 1303 ms 187544 KB Output is correct
22 Correct 1297 ms 187432 KB Output is correct
23 Correct 1335 ms 187688 KB Output is correct
24 Correct 1541 ms 187380 KB Output is correct
25 Correct 1338 ms 186880 KB Output is correct