Submission #617693

#	Time	Username	Problem	Language	Result	Execution time	Memory
617693		talant117408	Election (BOI18_election)	C++17	0 / 100	1 ms	492 KiB

election

#include <bits/stdc++.h>
//~ #include <ext/pb_ds/assoc_container.hpp> // Общий файл. 
//~ #include <ext/pb_ds/tree_policy.hpp> // Содержит класс tree_order_statistics_node_update
 
using namespace std;
//~ using namespace __gnu_pbds;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
//~ typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
 
#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'
#define PI                  2*acos(0.0)

const int N = 5e5+7;
int tree[N * 4];
int suff[N];

void build(int v, int l, int r) {
    if (l == r) {
        tree[v] = suff[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(v * 2, l, mid);
    build(v * 2 + 1, mid + 1, r);
    tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
}

int get(int v, int l, int r, int ql, int qr) {
    if (ql > r || l > qr) return 2e9;
    if (ql <= l && r <= qr) return tree[v];
    int mid = (l + r) >> 1;
    return min(get(v * 2, l, mid, ql, qr), get(v * 2 + 1, mid + 1, r, ql, qr));
}

void solve(int test) {
    int q, n;
    string s;
    cin >> n >> s >> q;
    int balance = 0;
    vector <int> weight(n);
    vector <int> deleted;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == 'T') {
            deleted.pb(i);
            weight[i] = -1;
        }
        else {
            if (sz(deleted)) {
                deleted.pop_back();
            }
            weight[i] = 1;
        }
    }
    for (auto to : deleted) weight[to] = 0;
    reverse(all(deleted));
    for (int i = n - 1; i >= 0; i--) {
        balance += weight[i];
        suff[i] = balance;
    }
    build(1, 0, n - 1);
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        auto L = lb(all(deleted), l) - deleted.begin();
        auto R = ub(all(deleted), r) - deleted.begin();
        cout <<  R - L + max(0, -(get(1, 0, n - 1, l, r) - suff[r + 1])) << endl;
    }
}
 
int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    for (int i = 1; i <= t; i++) {
        solve(i);
    }
    
    return 0;
}

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