Submission #867197

#	Time	Username	Problem	Language	Result	Execution time	Memory
867197		Markynoodle	Election (BOI18_election)	C++17	100 / 100	480 ms	28024 KiB

election

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

#define all(x) x.begin(),x.end()
#define ll long long
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
auto cmp = [](int a, int b){return a > b;};
auto cmp1 = [](pair<ll,ll> a, pair<ll,ll> b){
    if(a.first == b.first)return a.second > b.second;
    return a.first < b.first;
    };
ll mod = 1000000007;


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

#define ll long long
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr);

int nextpowerof2(int n){
    return 1<<(__lg(n-1)+1);
}

struct node{
    int sum;
    int pre;
    int suf;
    int ans;
};

node merge(node a, node b){
    return {a.sum + b.sum, max(a.pre, a.sum + b.pre), max(b.suf, b.sum + a.suf), max({0, a.pre + b.suf, a.ans + b.sum, a.sum + b.ans})};
}

struct segtree{
    vector<node> tree;
    segtree(int n) : tree(){
        tree.assign(n, {0,0,0,0});
    };
    void update(int l, int r, int pos, int i, int x){

        if(l == i && l + 1 == r){
            tree[pos] = {x, max(x, 0), max(x, 0), max(x, 0)};
            return;
        }
        if(i < l || r <= i)return;
        int m = l + (r - l)/2;

        update(l, m, pos*2, i, x);
        update(m, r, pos*2 + 1, i, x);
        tree[pos] = merge(tree[pos*2], tree[pos*2 + 1]);
        return;
    }

    node query(int l, int r, int pos, int ql, int qr){
        if(ql <= l && r <= qr)return tree[pos];
        if(qr <= l || r <= ql)return {0,0,0,0};
        int m = l + (r - l)/2;
        return merge(query(l, m, pos*2, ql, qr), query(m, r, pos*2 + 1, ql, qr));
    }
};

int main(){
    fastIO
    int n;
    int q;
    cin>>n;
    int npo2 = nextpowerof2(n);
    segtree sgt(npo2 * 2);
    string s;
    cin>>s;
    for(int i =0; i<n; i++){
        if(s[i] == 'C')sgt.update(0, npo2, 1, i, -1);
        if(s[i] == 'T')sgt.update(0, npo2, 1, i, 1);
    }
    cin>>q;
    int x, y;

    for(int i =0; i<q;i++){

        cin>>x>>y;
        x--;
        cout<<sgt.query(0, npo2, 1, x, y).ans<<"\n";
    }
}

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