oj.uz

Submission #549486

# Submission time Handle Problem Language Result Execution time Memory
549486 2022-04-15T22:01:17 Z MohamedFaresNebili Election (BOI18_election) C++14
100 / 100
 512 ms 28004 KB 
#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

        using namespace std;

        using ll = long long;
        using ii = pair<ll, ll>;
        using vi = vector<int>;

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) (x).begin(), (x).end()
        #define lb lower_bound
        /// #define int ll

        const int oo = 1e9 + 7;

        int n, q; string s;
        struct node{
            int S, pr, sf, ans;
        } st[2000001];

        node merge(node u, node v) {
            node res;
            res.S = u.S + v.S;
            res.pr = max(u.pr, u.S + v.pr);
            res.sf = max(v.sf, v.S + u.sf);
            res.ans = max({u.pr + v.sf, u.ans + v.S, u.S + v.ans});
            return res;
        }
        void build(int v, int l, int r) {
            if(l == r) {
                if(s[l] == 'C') st[v] = {-1, 0, 0, 0};
                else st[v] = {1, 1, 1, 1};
                return;
            }
            build(v * 2, l, (l + r) / 2);
            build(v * 2 + 1, (l + r) / 2 + 1, r);
            st[v] = merge(st[v * 2], st[v * 2 + 1]);
        }
        node query(int v, int l, int r, int lo, int hi) {
            if(l > hi || r < lo) return {0, 0, 0, 0};
            if(l >= lo && r <= hi) return st[v];
            return merge(query(v * 2, l, (l + r) / 2, lo, hi),
                         query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
        }

		int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> n >> s >> q; build(1, 0, n - 1);
            while(q--) {
                int l, r; cin >> l >> r; l--; r--;
                cout << query(1, 0, n - 1, l, r).ans << "\n";
            }
		}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 49 ms 5764 KB Output is correct
7 Correct 56 ms 5764 KB Output is correct
8 Correct 51 ms 5632 KB Output is correct
9 Correct 43 ms 5696 KB Output is correct
10 Correct 46 ms 5672 KB Output is correct
11 Correct 47 ms 5780 KB Output is correct
12 Correct 55 ms 5788 KB Output is correct
13 Correct 48 ms 5836 KB Output is correct
14 Correct 50 ms 5836 KB Output is correct
15 Correct 69 ms 5752 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 49 ms 5764 KB Output is correct
7 Correct 56 ms 5764 KB Output is correct
8 Correct 51 ms 5632 KB Output is correct
9 Correct 43 ms 5696 KB Output is correct
10 Correct 46 ms 5672 KB Output is correct
11 Correct 47 ms 5780 KB Output is correct
12 Correct 55 ms 5788 KB Output is correct
13 Correct 48 ms 5836 KB Output is correct
14 Correct 50 ms 5836 KB Output is correct
15 Correct 69 ms 5752 KB Output is correct
16 Correct 461 ms 26936 KB Output is correct
17 Correct 412 ms 26592 KB Output is correct
18 Correct 433 ms 26912 KB Output is correct
19 Correct 346 ms 26248 KB Output is correct
20 Correct 478 ms 25996 KB Output is correct
21 Correct 512 ms 27904 KB Output is correct
22 Correct 447 ms 27744 KB Output is correct
23 Correct 464 ms 28004 KB Output is correct
24 Correct 478 ms 27576 KB Output is correct
25 Correct 495 ms 27112 KB Output is correct