Submission #566117

#	Time	Username	Problem	Language	Result	Execution time	Memory
566117		birthdaycake	Election (BOI18_election)	C++17	100 / 100	379 ms	26752 KiB

election

#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 (stderr)

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 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18