oj.uz

Submission #941254

# Submission time Handle Problem Language Result Execution time Memory
941254 2024-03-08T11:45:10 Z NotLinux Election (BOI18_election) C++17
100 / 100
 541 ms 81524 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define int long long
struct Node {
    int sum, ans, pref, suf;
};
struct SegTree {
    int n;
    vector<Node> tree;
    vector<int> v;
 
    SegTree(vector<int> _v) {
        v = _v;
        n = sz(v);
        tree.resize(4*n+5);
        build(1, 0, n-1);
    }
 
    Node merge(Node a, Node b) {
        Node res;
 
        res.sum = a.sum + b.sum;
        res.pref = max({ (int)0, a.pref, a.sum + b.pref });
        res.suf = max({ (int)0, b.suf, b.sum + a.suf });
        res.ans = max({ a.pref + b.suf, a.ans + b.sum, a.sum + b.ans });
 
        return res;
    }
 
    void build(int u, int tl, int tr) {
        if(tl == tr) {
            tree[u].ans = max(v[tl], (int)0);
            tree[u].sum = v[tl];
            tree[u].pref = tree[u].suf = max(v[tl], (int)0);
        } else {
            int tm = (tl + tr) / 2;
            build(2*u, tl, tm);
            build(2*u+1, tm+1, tr);
            tree[u] = merge(tree[2*u], tree[2*u+1]);
        }
    }
 
    Node query(int u, int tl, int tr, int l, int r) {
        if(tl > tr || tl > r || l > tr) return Node{0, 0, 0, 0};
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return merge(query(2*u, tl, tm, l, r),query(2*u+1, tm+1, tr, l, r));
    }
 
    int query(int l, int r) {
        return query(1, 0, n-1, l, r).ans;
    }
};
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin >> n;
 
    vector<int> v(n);
    for(int i=0; i<n; i++) {
        char ch;
        cin >> ch;
        v[i] = (ch == 'T' ? 1 : -1);
    }
 
    SegTree tree(v);
    
    int q;
    cin >> q;
 
    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << tree.query(l-1, r-1) << '\n';
    } 
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 49 ms 11376 KB Output is correct
7 Correct 54 ms 11416 KB Output is correct
8 Correct 47 ms 11312 KB Output is correct
9 Correct 42 ms 11336 KB Output is correct
10 Correct 46 ms 11312 KB Output is correct
11 Correct 51 ms 11568 KB Output is correct
12 Correct 49 ms 11568 KB Output is correct
13 Correct 48 ms 11568 KB Output is correct
14 Correct 47 ms 11516 KB Output is correct
15 Correct 58 ms 11664 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 49 ms 11376 KB Output is correct
7 Correct 54 ms 11416 KB Output is correct
8 Correct 47 ms 11312 KB Output is correct
9 Correct 42 ms 11336 KB Output is correct
10 Correct 46 ms 11312 KB Output is correct
11 Correct 51 ms 11568 KB Output is correct
12 Correct 49 ms 11568 KB Output is correct
13 Correct 48 ms 11568 KB Output is correct
14 Correct 47 ms 11516 KB Output is correct
15 Correct 58 ms 11664 KB Output is correct
16 Correct 515 ms 80460 KB Output is correct
17 Correct 382 ms 79996 KB Output is correct
18 Correct 451 ms 80380 KB Output is correct
19 Correct 383 ms 79884 KB Output is correct
20 Correct 489 ms 79648 KB Output is correct
21 Correct 521 ms 81392 KB Output is correct
22 Correct 526 ms 81164 KB Output is correct
23 Correct 524 ms 81524 KB Output is correct
24 Correct 541 ms 81168 KB Output is correct
25 Correct 524 ms 80480 KB Output is correct