Submission #617794

#	Time	Username	Problem	Language	Result	Execution time	Memory
617794		talant117408	Election (BOI18_election)	C++17	100 / 100	641 ms	47424 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;
pii tree[N * 4];
int weight[N];

pii combine(pii a, pii b) {
    return mp(a.first + b.first, max(b.second, a.second + b.first));
}

void update(int v, int l, int r, int pos, int val) {
    if (l == r) {
        tree[v].first = val;
        tree[v].second = max(0, val);
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) update(v * 2, l, mid, pos, val);
    else update(v * 2 + 1, mid + 1, r, pos, val);
    tree[v] = combine(tree[v * 2], tree[v * 2 + 1]);
}

pii get(int v, int l, int r, int ql, int qr) {
    if (ql > r || l > qr) return mp(0, 0);
    if (ql <= l && r <= qr) return tree[v];
    int mid = (l + r) >> 1;
    return combine(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;
    vector <int> queries[n], ans(q);
    vector <int> l(q), r(q);
    for (int i = 0; i < q; i++) {
        cin >> l[i] >> r[i];
        r[i]--; l[i]--;
        queries[l[i]].pb(i);
    }
    deque <int> deleted;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == 'T') {
            deleted.push_front(i);
        }
        else {
            if (sz(deleted)) {
                update(1, 0, n - 1, deleted.front(), 1);
                deleted.pop_front();
            }
            update(1, 0, n - 1, i, -1);
        }
        for (auto j : queries[i]) {
            auto del = ub(all(deleted), r[j]) - deleted.begin();
            auto res = get(1, 0, n - 1, i, r[j]);
            ans[j] = res.second + del;
        }
    }
    for (auto to : ans) cout << to << endl;
}
 
int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    for (int i = 1; i <= t; i++) {
        solve(i);
    }
    
    return 0;
}

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