Submission #760553

#	Time	Username	Problem	Language	Result	Execution time	Memory
760553		vjudge1	Election (BOI18_election)	C++17	100 / 100	1930 ms	82096 KiB

election

#include <bits/stdc++.h>
#define ve vector
#define vi vector<int>
#define vii vector<ii>
#define ii pair<int,int>
#define fi first
#define se second
#define ll long long
#define INF 1e9+7
#define pb push_back
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag,
    tree_order_statistics_node_update>;
const int MOD = 1e9+7;
const int nax = 5e5+5;
void readio(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}
vi st[nax*4]{vi(4)};
vi merge(vi a, vi b){
    vi res(4);
    res[0] = a[0]+b[0];
    res[1] = max(a[1], b[1]+a[0]);
    res[2] = max(b[2], a[2]+b[0]);
    res[3] = max(max(max(a[3]+b[0], b[3]+a[0]),0), a[1]+b[2]);
    return res;
}
string s;
void build(int v, int l, int r){
    if(l == r){
        int a = (s[l] == 'T'), b = a;
        if(b == 0) b--;
        st[v] = {b,a,a,a};
        return;
    }
    int md = (l+r)/2;
    build(v*2,l,md);
    build(v*2+1,md+1,r);
    st[v] = merge(st[v*2], st[v*2+1]);
    //cout << l << " " << r << ' ' << st[v][3] << endl;
}
vi query(int v, int l, int r, int i, int j){
    if(i > r || j < l) return {0,0,0,0};
    if(i <= l && r <= j) return st[v];
    int md = (l+r)/2;
    return merge(query(v*2,l,md, i , j), query(v*2+1, md+1, r, i , j));
}
int main()
{
    optimise;
    int n;
    cin >> n;
    cin >> s;
    build(1,0,n-1);
    int q;
    cin >> q;
    while(q--){
        int l,r;
        cin >> l >> r;
        l--,r--;
        cout << query(1,0,n-1, l, r)[3] << endl;
    }
}

Compilation message (stderr)

election.cpp: In function 'void readio()':
election.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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