oj.uz

Submission #566117

# Submission time Handle Problem Language Result Execution time Memory
566117 2022-05-21T20:16:40 Z birthdaycake Election (BOI18_election) C++17
100 / 100
 379 ms 26752 KB 
#include<bits/stdc++.h>
#define endl '\n'
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);
using namespace std;
 
 
 
int N,Left,Right;
struct node{
    int mxp, mxs, tot, ans;
};

node seg[2000001];
vector<node>ans;



void Query(int l = 1, int r = N, int ind = 1){
    if(l > Right || r < Left) return;
    if(l >= Left && r <= Right){
        ans.push_back(seg[ind]);
        return;
    }
    int mid = (l + r) /2;
    Query(l, mid, ind * 2);
    Query(mid + 1, r, ind * 2 + 1);
}





signed main(){
    boost;
    
    
    
    
    
    int n; cin >> n;
    string a; cin >> a;
    
    N = exp2(ceil(log2(n)));
    
    
    for(int i = 0; i < a.size(); i++){
        seg[i + N].tot = (a[i] == 'C' ? -1 : 1);
        if(seg[i + N].tot == 1) seg[i + N].ans = seg[i + N].mxs = seg[i + N].mxp = seg[i + N].tot;
    }
    for(int i = N - 1 ; i > 0; i--){
        seg[i].tot = seg[i * 2].tot + seg[i * 2 + 1].tot;
        seg[i].mxp = max(seg[i * 2].mxp, seg[i * 2].tot + seg[i * 2 + 1].mxp);
        seg[i].mxs = max(seg[i * 2 + 1].mxs, seg[i * 2 + 1].tot + seg[i * 2].mxs);
        seg[i].ans = max({seg[i * 2].mxp + seg[i * 2 + 1].mxs, seg[i * 2].ans + seg[i * 2 + 1].tot, seg[i * 2 + 1].ans + seg[i * 2].tot});
    }
    
    int q; cin >> q;
    while(q--){
        cin >> Left >> Right;
        int as = 0, mxp = 0, mxs = 0, t = 0;
        Query();
        for(int i = 0; i < ans.size(); i++){
            as = max({mxp + ans[i].mxs, t + ans[i].ans, as + ans[i].tot});
            mxp = max(mxp, t + ans[i].mxp);
            mxs = max(mxs + ans[i].tot, ans[i].mxs);
            t += ans[i].tot;
        }
        cout << as << endl;
        
        
        ans.clear();
        
    }
    
    return 0;
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i = 0; i < a.size(); i++){
      |                    ~~^~~~~~~~~~
election.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int i = 0; i < ans.size(); i++){
      |                        ~~^~~~~~~~~~~~

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 41 ms 4748 KB Output is correct
7 Correct 39 ms 4812 KB Output is correct
8 Correct 37 ms 4684 KB Output is correct
9 Correct 35 ms 4772 KB Output is correct
10 Correct 40 ms 4688 KB Output is correct
11 Correct 39 ms 4892 KB Output is correct
12 Correct 40 ms 4812 KB Output is correct
13 Correct 40 ms 4932 KB Output is correct
14 Correct 39 ms 4812 KB Output is correct
15 Correct 38 ms 4836 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 41 ms 4748 KB Output is correct
7 Correct 39 ms 4812 KB Output is correct
8 Correct 37 ms 4684 KB Output is correct
9 Correct 35 ms 4772 KB Output is correct
10 Correct 40 ms 4688 KB Output is correct
11 Correct 39 ms 4892 KB Output is correct
12 Correct 40 ms 4812 KB Output is correct
13 Correct 40 ms 4932 KB Output is correct
14 Correct 39 ms 4812 KB Output is correct
15 Correct 38 ms 4836 KB Output is correct
16 Correct 371 ms 26464 KB Output is correct
17 Correct 312 ms 25696 KB Output is correct
18 Correct 346 ms 25820 KB Output is correct
19 Correct 291 ms 25168 KB Output is correct
20 Correct 363 ms 24672 KB Output is correct
21 Correct 379 ms 26604 KB Output is correct
22 Correct 363 ms 26352 KB Output is correct
23 Correct 370 ms 26752 KB Output is correct
24 Correct 365 ms 26300 KB Output is correct
25 Correct 359 ms 25872 KB Output is correct