Submission #857295

#	Time	Username	Problem	Language	Result	Execution time	Memory
857295		Markynoodle	Election (BOI18_election)	C++17	0 / 100	2 ms	2140 KiB

election

#include <bits/stdc++.h>
using namespace std;
#define ll long long

bool cmpup(pair<int,int> a, pair<int,int> b){
    if(a.first == b.first)return a.second < b.second;
    return a.first < b.first;
}
bool cmpdown(pair<int,int> a, pair<int,int> b){
    if(a.first == b.first)return a.second > b.second;
    return a.first < b.first;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int lg = 19;
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<int> vals(n+2,0);
    vector<vector<pair<int,int>>> sparseup(n+5, vector<pair<int,int>>(lg+1, {0,0}));
    vector<vector<pair<int,int>>> sparsedown(n+5, vector<pair<int,int>>(lg+1, {0,0}));
    vector<int> prefix0(n+2, 0);
    for(int i =1; i<=n; i++){
        prefix0[i] = prefix0[i-1];
        if(s[i-1] == 'T')vals[i] = -1;
        if(s[i-1] == 'T')prefix0[i]++;
        if(s[i-1] == 'C')vals[i] = 1;
    }
    vector<int> prefixu(n+2, 0);
    for(int i =1; i<=n; i++){
        prefixu[i] = prefixu[i-1] + vals[i];
        //cout<<prefixu[i]<<" ";
        sparseup[i][0] = {prefixu[i], i};
    }
    vector<int> prefixd(n+3, 0);
    for(int i =n; i>=1; i--){
        prefixd[i] = prefixd[i+1] + vals[i];
        sparsedown[i][0] = {prefixd[i], i};
    }
    //for(auto k : prefixd)cout<<k<<" ";
    //cout<<"\n";
    for(int j = 1; j<lg; j++){
        for(int i = 1; i<= n - (1<<j)+1; i++){
            bool first = cmpup(sparseup[i][j-1], sparseup[i + (1<<(j-1))][j-1]);
            if(first)sparseup[i][j] = sparseup[i][j-1];
            else sparseup[i][j] = sparseup[i + (1<<(j-1))][j-1];
        }
    }
    for(int j = 1; j<lg; j++){
        for(int i = 1; i<= n - (1<<j)+1; i++){
            bool first = cmpdown(sparsedown[i][j-1], sparsedown[i + (1<<(j-1))][j-1]);
            if(first)sparsedown[i][j] = sparsedown[i][j-1];
            else sparsedown[i][j] = sparsedown[i + (1<<(j-1))][j-1];
        }
    }
    //for(auto k : prefixu)cout<<k<<" ";
    //cout<<"\n";
    int q;
    cin>>q;
    for(int i =0; i<q; i++){

        int x, y;
        cin>>x>>y;
        int start = prefixu[x-1];
        int fin = prefixd[y+1];
        pair<int,int> up;
        pair<int,int> down;
        int dif = y - x + 1;
        int p2 = __lg(dif - 1);
        bool f = cmpup(sparseup[x][p2], sparseup[y - (1<<p2) + 1][p2]);
        if(f)up = sparseup[x][p2];
        else up = sparseup[y - (1<<p2) + 1][p2];
        f = cmpdown(sparsedown[x][p2], sparsedown[y - (1<<p2) + 1][p2]);
        if(f) down = sparsedown[x][p2];
        else down = sparsedown[y - (1<<p2) + 1][p2];
        //cout<<up.second<<" "<<down.second<<" ";/////

        if(up.second < down.second){
            int sol = max(0, start - up.first);
            sol += max(0, fin - down.first);
            //cout<<sol<<"\n";
            continue;
        }

        else{
            int xx = down.second;
            int yy = up.second;
            int sol = 0;
            int zeros = prefix0[yy] - prefix0[xx-1];
            int ones = yy - xx + 1 - zeros;
            xx--;
            yy++;
            if(xx >= x){
            p2 = __lg(xx - x);
            f = cmpup(sparseup[x][p2], sparseup[xx - (1<<p2)+1][p2]);
            if(f)sol += max(0, start - sparseup[x][p2].first);
            else sol += max(0, start - sparseup[xx - (1<<p2)+1][p2].first);
            }
            int addeda = sol;
            //cout<<sol<<" ";
            if(yy <= y){
            p2 = __lg(y - yy);
            f = cmpup(sparsedown[yy][p2], sparsedown[y - (1<<p2)+1][p2]);
            //cout<<fin<<": "<<p2<<": ";
            //if(f)cout<<":::";
            if(f)sol += max(0, fin - sparsedown[yy][p2].first);
            else sol += max(0, fin - sparsedown[y - (1<<p2)+1][p2].first);
            }
            int addedb = sol-addeda;
            //cout<<sol<<" ";
            //cout<<ones<<" "<<zeros<<" ";
            yy--;
            xx++;
            int bonusa = prefixu[xx-1] - prefixu[x-1] + addeda;
            bonusa = max(0, bonusa);
            //cout<<yy+1<<" "<<y+1<<" ";
            int bonusb = prefixd[yy+1] - prefixd[y+1] + addedb;
            //cout<<"\n,,";
            //cout<<prefixd[yy+1]<<" "<<prefixd[y+1]<<" ";
            bonusb = max(0, bonusb);
            int neg = zeros - ones;
            //cout<<bonusa<<" "<<bonusb<<" "<<neg<<"  ";
            sol += max(0,(max(neg - bonusa, neg - bonusb)));
            cout<<sol<<"\n";
        }

    }
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18