Submission #699185

#	Time	Username	Problem	Language	Result	Execution time	Memory
699185		bane	Election (BOI18_election)	C++17	100 / 100	428 ms	28000 KiB

election

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<deque>
#include<map>
#include<set>
#include<unordered_set>
#include<math.h>
//#include<bits/stdc++.h>
using namespace std;
 
#ifdef LOCAL
    #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
    #define eprintf(...) 42
#endif
 
#define pb push_back
#define mp make_pair
#define ins insert
#define popb pop_back
#define popf pop_front
#define ft front
#define bk back
#define fr first
#define sc second
using ll = long long;
using ld = long double;
using db = double;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<ld,ld>;
using str = string;
const int NAX = (int)1e5 + 1;
const int MOD = (int)1e9 + 7;
int n, q;
string s;
struct Node{
    int P,S,T,A;
    Node operator+(Node a){
        Node ans;
        ans.P = max(T + a.P, P);
        ans.S = max(a.S, a.T + S);
        ans.T = T + a.T;
        ans.A = max(max(A + a.T, a.A + T), P + a.S);
        return ans;
    }
};
template<class V, int NV>class SegmentTree{
public:
    Node t[NV * 3];
    
    void build(int l = 0, int r = n - 1, int k = 1){
        if (l == r){
            if (s[l] == 'T') t[k] = {1, 1, 1, 1};
            else t[k] = {0, 0, -1, 0};
            return ;
        }
        int mid = (l + r) / 2;
        build(l, mid, k * 2);
        build(mid + 1, r, k * 2 | 1);
        t[k] = t[k * 2] + t[k * 2 | 1];
    }
    Node query(int lef, int rig, int l = 0, int r = n - 1, int k = 1){
        if (r < lef || l > rig)return {0,0,0,0};
        if (l>=lef && r <= rig)return t[k];
        return query(lef,rig,l,(r+l)/ 2, k * 2) + query(lef,rig, (l+r)/2+1,r,1+k*2);
    }
};
SegmentTree<int, (1<<20)>st;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s >> q;
    // [l...r]
    //[CCCTTTCCTTT...]
    //find how many erasers are needed using segment tree from one side
    st.build();
    while(q--){
        int a,b;
        cin >>  a >> b;
        cout<<st.query(--a,--b).A<<'\n';
    }
    return 0;
}

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