oj.uz

Submission #479648

# Submission time Handle Problem Language Result Execution time Memory
479648 2021-10-12T15:24:43 Z CodeChamp_SS Election (BOI18_election) C++17
100 / 100
 564 ms 28104 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ff                  first
#define ss                  second
#define pb                  push_back
#define eb                  emplace_back
#define mp                  make_pair
#define lb                  lower_bound
#define ub                  upper_bound
#define setbits(x)          __builtin_popcountll(x)
#define zrobits(x)          __builtin_ctzll(x)
#define sz(v)               (int)v.size()
#define ps(y)               cout << fixed << setprecision(y)
#define ms(arr, v)          memset(arr, v, sizeof(arr))
#define all(v)              v.begin(), v.end()
#define rall(v)             v.rbegin(), v.rend()
#define trav(x, v)          for(auto &x: v)
#define w(t)                int t; cin >> t; while(t--)
#define rep(i, a, b)        for(int i = a; i <= b; i++)
#define rrep(i, a, b)       for(int i = a; i >= b; i--)
#define rep0(i, n)          rep(i, 0, n - 1)
#define rrep0(i, n)         rrep(i, n - 1, 0)
#define rep1(i, n)          rep(i, 1, n)
#define rrep1(i, n)         rrep(i, n, 1)
#define inp(arr, n)         rep0(i, n) cin >> arr[i];

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef map<ll, ll> mii;
typedef map<char, ll> mci;
typedef priority_queue<ll> pq_mx;
typedef priority_queue<ll, vi, greater<>> pq_mn;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> pbds;
/*
 * find_by_order(i) -> returns an iterator to the element at ith position (0 based)
 * order_of_key(i)  -> returns the position of element i (0 based)
 */

const int N = 5e5 + 5;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll inf = 2e18;
const ld eps = 1e-10, pi = acos(-1.0);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void fio() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
}

ll n, q;
string S;

struct Node {
    int lmx = 0, rmx = 0, sum = 0, mx = 0;
};

struct SegTree {
    Node st[4 * N]{}, dummy{};

    Node combine(Node l, Node r) {
        return {
                max(l.lmx, l.sum + r.lmx),
                max(r.rmx, r.sum + l.rmx),
                l.sum + r.sum,
                max(l.lmx + r.rmx, max(l.mx + r.sum, l.sum + r.mx))
        };
    }

    void build(ll s = 0, ll e = n - 1, int idx = 1) {
        if (s == e) {
            st[idx] = ((S[s] == 'T') ? Node{1, 1, 1, 1} : Node{0, 0, -1, 0});
            return;
        }

        ll m = s + (e - s) / 2;
        build(s, m, 2 * idx), build(m + 1, e, 2 * idx + 1);
        st[idx] = combine(st[2 * idx], st[2 * idx + 1]);
    }

    Node query(ll qs, ll qe, ll s = 0, ll e = n - 1, int idx = 1) {
        if (qs > e or qe < s) return dummy;

        if (s >= qs and e <= qe) return st[idx];

        ll mid = s + (e - s) / 2;
        Node lft = query(qs, qe, s, mid, 2 * idx), rt = query(qs, qe, mid + 1, e, 2 * idx + 1);
        return combine(lft, rt);
    }
} st;

int main() {
    fio();

    cin >> n >> S >> q;

    st.build();
    rep0(x, q) {
        int l, r;
        cin >> l >> r, --l, --r;
        cout << st.query(l, r).mx << '\n';
    }

    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 51 ms 5776 KB Output is correct
7 Correct 54 ms 5744 KB Output is correct
8 Correct 54 ms 5644 KB Output is correct
9 Correct 66 ms 5704 KB Output is correct
10 Correct 56 ms 5692 KB Output is correct
11 Correct 56 ms 5836 KB Output is correct
12 Correct 54 ms 5832 KB Output is correct
13 Correct 54 ms 5820 KB Output is correct
14 Correct 70 ms 5804 KB Output is correct
15 Correct 55 ms 5788 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 51 ms 5776 KB Output is correct
7 Correct 54 ms 5744 KB Output is correct
8 Correct 54 ms 5644 KB Output is correct
9 Correct 66 ms 5704 KB Output is correct
10 Correct 56 ms 5692 KB Output is correct
11 Correct 56 ms 5836 KB Output is correct
12 Correct 54 ms 5832 KB Output is correct
13 Correct 54 ms 5820 KB Output is correct
14 Correct 70 ms 5804 KB Output is correct
15 Correct 55 ms 5788 KB Output is correct
16 Correct 524 ms 27100 KB Output is correct
17 Correct 442 ms 26516 KB Output is correct
18 Correct 478 ms 26812 KB Output is correct
19 Correct 404 ms 26316 KB Output is correct
20 Correct 534 ms 26084 KB Output is correct
21 Correct 524 ms 27852 KB Output is correct
22 Correct 526 ms 27720 KB Output is correct
23 Correct 526 ms 28104 KB Output is correct
24 Correct 564 ms 27612 KB Output is correct
25 Correct 527 ms 27232 KB Output is correct