oj.uz

Submission #617794

# Submission time Handle Problem Language Result Execution time Memory
617794 2022-08-01T14:25:56 Z talant117408 Election (BOI18_election) C++17
100 / 100
 641 ms 47424 KB 
#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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 564 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 476 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 564 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 476 KB Output is correct
6 Correct 54 ms 7460 KB Output is correct
7 Correct 48 ms 6628 KB Output is correct
8 Correct 49 ms 6916 KB Output is correct
9 Correct 62 ms 7364 KB Output is correct
10 Correct 57 ms 7372 KB Output is correct
11 Correct 61 ms 7804 KB Output is correct
12 Correct 58 ms 7524 KB Output is correct
13 Correct 56 ms 7116 KB Output is correct
14 Correct 57 ms 7496 KB Output is correct
15 Correct 52 ms 7468 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 564 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 476 KB Output is correct
6 Correct 54 ms 7460 KB Output is correct
7 Correct 48 ms 6628 KB Output is correct
8 Correct 49 ms 6916 KB Output is correct
9 Correct 62 ms 7364 KB Output is correct
10 Correct 57 ms 7372 KB Output is correct
11 Correct 61 ms 7804 KB Output is correct
12 Correct 58 ms 7524 KB Output is correct
13 Correct 56 ms 7116 KB Output is correct
14 Correct 57 ms 7496 KB Output is correct
15 Correct 52 ms 7468 KB Output is correct
16 Correct 560 ms 46296 KB Output is correct
17 Correct 485 ms 39920 KB Output is correct
18 Correct 489 ms 42328 KB Output is correct
19 Correct 490 ms 44436 KB Output is correct
20 Correct 613 ms 45392 KB Output is correct
21 Correct 641 ms 47424 KB Output is correct
22 Correct 595 ms 47016 KB Output is correct
23 Correct 622 ms 46144 KB Output is correct
24 Correct 601 ms 46420 KB Output is correct
25 Correct 551 ms 46416 KB Output is correct