oj.uz

Submission #647493

# Submission time Handle Problem Language Result Execution time Memory
647493 2022-10-02T21:51:17 Z UltraFalcon Election (BOI18_election) C++17
100 / 100
 500 ms 43904 KB 
#ifndef DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,abm,mmx,fma,popcnt")
#endif

#include <bits/stdc++.h>
#define int long long

using namespace std;

int next_power_of_two(int x) { return 1LL<<(__lg(x-1)+1); }

struct Value {
    int inc, dec, sum, ans;
    constexpr static Value Identity() { return {0, 0, 0, 0}; }
    static Value Single(char x) {
        int val = (x == 'C') ? 1 : -1; 
        return {val<0, val<0, val, val<0}; 
    }
    friend Value combine(Value a, Value b) {
        Value res;
        res.inc = a.inc + max(0LL, (b.inc - (a.sum + a.inc)));
        res.dec = b.dec + max(0LL, (a.dec - (b.sum + b.dec)));
        res.sum = a.sum + b.sum;
        res.ans = max({a.ans-b.sum, b.ans-a.sum, a.inc+b.dec});
        return res;
    }
};
struct Segtree {
    int n; 
    vector<Value> tree;

    Segtree(string& v) {
        n = next_power_of_two(v.size());
        tree.assign(2*n, Value::Identity());
        build(v, 0, 0, n);
    }

    public:
    Value query(int ql, int qr) {
        assert(0 <= ql && ql < qr && qr <= n);
        return query(ql, qr, 0, 0, n);
    }


    private:
    void recompute(int pos) {
        tree[pos] = combine(tree[pos*2+1], tree[pos*2+2]);
    }

    void build(string&v, int pos, int l, int r) {
        if (l >= (int)v.size()) return;
        if (l+1 == r) { tree[pos]=Value::Single(v[l]); return; }
        int m = (l+r) / 2;
        build(v, pos*2+1, l, m);
        build(v, pos*2+2, m, r);
        recompute(pos);
    }

    Value query(int ql, int qr, int pos, int l, int r) {
        if (ql >= r || qr <= l) return Value::Identity();
        if (ql <= l && qr >= r) return tree[pos];
        int m = (l+r) / 2;
        return combine(
            query(ql, qr, pos*2+1, l, m),
            query(ql, qr, pos*2+2, m, r)
        );
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    // Value a = {0, 2, 1};
    // Value b = {4, 2, -2};
    // Value res = combine(a, b);
    // cout << res.inc << " " << res.dec << "\n";

    int n; cin >> n;
    string votes; cin >> votes;
    
    Segtree seg(votes);
    
    int q; cin >> q;
    for (int i=0; i<q; i++) {
        int l, r;
        cin >> l >> r;
        Value res = seg.query(l-1, r);
        cout << res.ans << "\n";
    }

}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 53 ms 9896 KB Output is correct
7 Correct 46 ms 9824 KB Output is correct
8 Correct 55 ms 9740 KB Output is correct
9 Correct 48 ms 9784 KB Output is correct
10 Correct 54 ms 9760 KB Output is correct
11 Correct 50 ms 9880 KB Output is correct
12 Correct 49 ms 9932 KB Output is correct
13 Correct 57 ms 9920 KB Output is correct
14 Correct 58 ms 10056 KB Output is correct
15 Correct 61 ms 9868 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 53 ms 9896 KB Output is correct
7 Correct 46 ms 9824 KB Output is correct
8 Correct 55 ms 9740 KB Output is correct
9 Correct 48 ms 9784 KB Output is correct
10 Correct 54 ms 9760 KB Output is correct
11 Correct 50 ms 9880 KB Output is correct
12 Correct 49 ms 9932 KB Output is correct
13 Correct 57 ms 9920 KB Output is correct
14 Correct 58 ms 10056 KB Output is correct
15 Correct 61 ms 9868 KB Output is correct
16 Correct 482 ms 42856 KB Output is correct
17 Correct 423 ms 42460 KB Output is correct
18 Correct 452 ms 42744 KB Output is correct
19 Correct 402 ms 42116 KB Output is correct
20 Correct 484 ms 41896 KB Output is correct
21 Correct 500 ms 43768 KB Output is correct
22 Correct 488 ms 43712 KB Output is correct
23 Correct 480 ms 43904 KB Output is correct
24 Correct 480 ms 43464 KB Output is correct
25 Correct 492 ms 42968 KB Output is correct