Submission #699184

#	Time	Username	Problem	Language	Result	Execution time	Memory
699184		bane	Election (BOI18_election)	C++17	0 / 100	2 ms	340 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;
};
template<class V, int NV>class SegmentTree{
public:
    Node t[NV * 3];
    void merge(int node){
        int l = node * 2;
        int r = node * 2 | 1;
        t[node].P = max(t[l].T + t[r].P, t[l].P);
        t[node].S = max(t[r].S, t[r].T + t[l].S);
        t[node].T = t[l].T + t[r].T;
        t[node].A = max(max(t[l].A + t[r].T, t[r].A + t[l].T), t[l].P + t[r].S);
    }
    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);
        merge(k);
    }
    int query(int lef, int rig, int l = 0, int r = n - 1, int k = 1){
        if (r < lef || l > rig)return 0;
        if (l>=lef && r <= rig)return t[k].A;
        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...]
  
    st.build();
    while(q--){
        int a,b;
        cin >>  a >> b;
        cout<<max(0, st.query(--a,--b))<<'\n';
    }
    return 0;
}

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