oj.uz

Submission #933895

# Submission time Handle Problem Language Result Execution time Memory
933895 2024-02-26T14:08:56 Z Whisper Election (BOI18_election) C++17
100 / 100
 574 ms 74148 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define pii pair<int , int>
#define Lg(x) 31 - __builtin_clz(x)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 5e5 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int nArr, numQuery;
string s;
struct SegTree{
    struct Node{
        int ans, sum, prf, suf;
        Node(): ans(0), sum(0), prf(0), suf(0){}
        Node(int x){
            sum = x;
            ans = max(0ll, x);
            prf = max(0ll, x);
            suf = max(0ll, x);
        }
        friend Node operator + (const Node& a, const Node& b){
            Node res;
            res.sum = a.sum + b.sum;
            res.prf = max(a.prf, a.sum + b.prf);
            res.suf = max(b.suf, b.sum + a.suf);
            res.ans = max({a.ans + b.sum, a.sum + b.ans, a.prf + b.suf});
            return res;
        }
    };
    vector<Node> st;
    int n;
    SegTree(int _n){
        this -> n = _n;
        st.resize((n << 2));
    }

    void BuildTree(int id, int l, int r){
        if (l == r){
            st[id] = Node((s[l] == 'C' ? -1 : 1));
            return;
        }
        int mid = (l + r) >> 1;
        BuildTree(id << 1, l, mid);
        BuildTree(id << 1 | 1, mid + 1, r);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    Node query(int id, int l, int r, int u, int v){
        if (u > r || v < l) return Node(0);
        if (u <= l && v >= r) return st[id];
        int mid = (l + r) >> 1;
        Node ql = query(id << 1, l, mid, u, v);
        Node qr = query(id << 1 | 1, mid + 1, r, u, v);
        return (ql + qr);
    }
};
void Whisper(){
    cin >> nArr >> s;
    s = '@' + s;
    cin >> numQuery;
    SegTree st(nArr + 1);
    st.BuildTree(1, 1, nArr);
    for (int i = 1; i <= numQuery; ++i){
        int l, r; cin >> l >> r;
        cout << st.query(1, 1, nArr, l, r).ans << '\n';
    }
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 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 600 KB Output is correct
2 Correct 1 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 38 ms 10596 KB Output is correct
7 Correct 36 ms 10484 KB Output is correct
8 Correct 39 ms 10324 KB Output is correct
9 Correct 46 ms 10316 KB Output is correct
10 Correct 39 ms 10316 KB Output is correct
11 Correct 41 ms 10576 KB Output is correct
12 Correct 38 ms 10580 KB Output is correct
13 Correct 39 ms 10704 KB Output is correct
14 Correct 54 ms 10572 KB Output is correct
15 Correct 53 ms 10464 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 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 38 ms 10596 KB Output is correct
7 Correct 36 ms 10484 KB Output is correct
8 Correct 39 ms 10324 KB Output is correct
9 Correct 46 ms 10316 KB Output is correct
10 Correct 39 ms 10316 KB Output is correct
11 Correct 41 ms 10576 KB Output is correct
12 Correct 38 ms 10580 KB Output is correct
13 Correct 39 ms 10704 KB Output is correct
14 Correct 54 ms 10572 KB Output is correct
15 Correct 53 ms 10464 KB Output is correct
16 Correct 574 ms 73112 KB Output is correct
17 Correct 361 ms 73232 KB Output is correct
18 Correct 370 ms 73208 KB Output is correct
19 Correct 341 ms 72620 KB Output is correct
20 Correct 438 ms 72384 KB Output is correct
21 Correct 467 ms 73984 KB Output is correct
22 Correct 437 ms 74012 KB Output is correct
23 Correct 413 ms 74148 KB Output is correct
24 Correct 476 ms 73980 KB Output is correct
25 Correct 431 ms 73440 KB Output is correct