Submission #1267351

#TimeUsernameProblemLanguageResultExecution timeMemory
1267351MisterReaperElection (BOI18_election)C++17
100 / 100
247 ms20948 KiB
// File A.cpp created on 05.09.2025 at 19:26:11 #include <bits/stdc++.h> using i64 = long long; #ifdef DEBUG #include "/home/ahmetalp/Desktop/Workplace/debug.h" #else #define debug(...) void(23) #endif struct node { int pre, suf, sum, ans; node() : pre(0), suf(0), sum(0), ans(0) {} node(int x) : pre(std::max(0, x)), suf(std::max(0, x)), sum(x), ans(std::max(0, x)) {} }; node operator+ (node lhs, node rhs) { node res; res.pre = std::max(lhs.pre, rhs.pre + lhs.sum); res.suf = std::max(rhs.suf, lhs.suf + rhs.sum); res.sum = lhs.sum + rhs.sum; res.ans = std::max({lhs.pre + rhs.suf, lhs.ans + rhs.sum, rhs.ans + lhs.sum}); return res; } #define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1) struct segtree { int n; std::vector<node> tree; segtree(std::vector<int>& x) : n(int(x.size())), tree(n << 1) { auto dfs = [&](auto&& self, int v, int l, int r) -> void { if (l == r) { tree[v] = {x[l]}; return; } def; self(self, lv, l, mid); self(self, rv, mid + 1, r); tree[v] = tree[lv] + tree[rv]; }; dfs(dfs, 0, 0, n - 1); } node get(int v, int l, int r, int ql, int qr) { if (ql == l && r == qr) { return tree[v]; } def; if (qr <= mid) { return get(lv, l, mid, ql, qr); } else if (mid + 1 <= ql) { return get(rv, mid + 1, r, ql, qr); } else { return get(lv, l, mid, ql, mid) + get(rv, mid + 1, r, mid + 1, qr); } } node get(int l, int r) { return get(0, 0, n - 1, l, r); } }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int N; std::cin >> N; std::vector<int> A(N); for (int i = 0; i < N; ++i) { char c; std::cin >> c; A[i] = c == 'C' ? -1 : +1; } segtree seg(A); int Q; std::cin >> Q; while (Q--) { int L, R; std::cin >> L >> R; --L, --R; node nd = seg.get(L, R); std::cout << nd.ans << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...