oj.uz

Submission #486944

# Submission time Handle Problem Language Result Execution time Memory
486944 2021-11-13T13:45:24 Z Victor Election (BOI18_election) C++17
100 / 100
 1348 ms 58444 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

string str;

struct Node {
    Node *l, *r;
    int lo, hi, sum, best, pref, suf;
    Node(int L, int R) : lo(L), hi(R) {
        if (hi - lo == 1) {
            sum = str[lo] == 'C' ? -1 : 1;
            best = pref = suf = max(sum, 0);

        } else {
            int mid = (lo + hi) / 2;
            l = new Node(lo, mid);
            r = new Node(mid, hi);

            best = max(max(l->best + r->sum, l->sum + r->best), l->pref + r->suf);
            sum = l->sum + r->sum;
            pref = max(l->pref, l->sum + r->pref);
            suf = max(r->suf, r->sum + l->suf);
        }
    }

    pair<ii, ii> query(int L, int R) {
        if (hi <= L || R <= lo) return {{0, 0}, {0, 0}};
        if (L <= lo && hi <= R) return {{sum, best}, {pref, suf}};

        int lsum, lbest, lpref, lsuf;
        auto val = l->query(L, R);
        tie(lsum, lbest) = val.first;
        tie(lpref, lsuf) = val.second;

        int rsum, rbest, rpref, rsuf;
        val = r->query(L, R);
        tie(rsum, rbest) = val.first;
        tie(rpref, rsuf) = val.second;

        int cur_best = max(max(lbest + rsum, lsum + rbest), lpref + rsuf);
        int cur_sum = lsum + rsum;
        int cur_pref = max(lpref, lsum + rpref);
        int cur_suf = max(rsuf, rsum + lsuf);

        return {{cur_sum, cur_best}, {cur_pref, cur_suf}};
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n, q;
    cin >> n >> str >> q;

    Node segtree(0, n);

    while (q--) {
        int lo, hi;
        cin >> lo >> hi;

        auto val = segtree.query(lo - 1, hi);
        int best = val.first.second, pref, suf;
        tie(pref, suf) = val.second;

        cout << max(best,max(pref,suf)) << endl;
    }
    return 0;
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 4 ms 452 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 139 ms 8116 KB Output is correct
7 Correct 124 ms 7988 KB Output is correct
8 Correct 131 ms 7988 KB Output is correct
9 Correct 127 ms 7960 KB Output is correct
10 Correct 141 ms 8004 KB Output is correct
11 Correct 142 ms 8232 KB Output is correct
12 Correct 136 ms 8236 KB Output is correct
13 Correct 138 ms 8140 KB Output is correct
14 Correct 153 ms 8140 KB Output is correct
15 Correct 145 ms 8136 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 4 ms 452 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 139 ms 8116 KB Output is correct
7 Correct 124 ms 7988 KB Output is correct
8 Correct 131 ms 7988 KB Output is correct
9 Correct 127 ms 7960 KB Output is correct
10 Correct 141 ms 8004 KB Output is correct
11 Correct 142 ms 8232 KB Output is correct
12 Correct 136 ms 8236 KB Output is correct
13 Correct 138 ms 8140 KB Output is correct
14 Correct 153 ms 8140 KB Output is correct
15 Correct 145 ms 8136 KB Output is correct
16 Correct 1324 ms 57452 KB Output is correct
17 Correct 1157 ms 56868 KB Output is correct
18 Correct 1189 ms 57332 KB Output is correct
19 Correct 1081 ms 56748 KB Output is correct
20 Correct 1331 ms 56620 KB Output is correct
21 Correct 1323 ms 58388 KB Output is correct
22 Correct 1348 ms 58280 KB Output is correct
23 Correct 1342 ms 58444 KB Output is correct
24 Correct 1342 ms 57928 KB Output is correct
25 Correct 1316 ms 57580 KB Output is correct