#include using namespace std; #define INF (ll) 1e15 using ll = long long; ll N, A; struct Node { ll lMax, rMax, aMax, aSum; }; struct SegTree { vector tree; SegTree() { ll S = 1; while (N > S) S <<= 1; tree.resize(S << 1); for (ll i = 0; i < N; i++) { tree[S+i] = {-INF, -INF, -INF, 0}; } } void update(ll node, ll start, ll end, ll idx, ll val) { if (start == end) { tree[node] = {val, val, val, val}; return; } ll mid = (start + end) >> 1; if (idx <= mid) update(node << 1, start, mid, idx, val); else update(node << 1 | 1, mid + 1, end, idx, val); Node& lNode = tree[node << 1]; Node& rNode = tree[node << 1 | 1]; Node& cNode = tree[node]; cNode.lMax = max(lNode.lMax, lNode.aSum + rNode.lMax); cNode.rMax = max(rNode.rMax, rNode.aSum + lNode.rMax); cNode.aMax = max({lNode.aMax, rNode.aMax, lNode.rMax + rNode.lMax}); cNode.aSum = lNode.aSum + rNode.aSum; } Node query(ll node, ll start, ll end, ll l, ll r) { if (r < start || end < l) { Node ret = {-INF, -INF, -INF, 0}; return ret; } if (l <= start && end <= r) { return tree[node]; } ll mid = (start + end) >> 1; Node lNode = query(node << 1, start, mid, l, r); Node rNode = query(node << 1 | 1, mid + 1, end, l, r); Node cNode; cNode.lMax = max(lNode.lMax, lNode.aSum + rNode.lMax); cNode.rMax = max(rNode.rMax, rNode.aSum + lNode.rMax); cNode.aMax = max({lNode.aMax, rNode.aMax, lNode.rMax + rNode.lMax}); cNode.aSum = lNode.aSum + rNode.aSum; return cNode; } }; int main() { cin.tie(0)->ios::sync_with_stdio(0); cin >> N; SegTree tree; for (ll i = 0; i < N; i++) { cin >> A; tree.update(1, 0, N-1, i, A); } ll M; cin >> M; ll x1, y1, x2, y2; while (M--) { cin >> x1 >> y1 >> x2 >> y2; if (y1 < x2) { Node lNode = tree.query(1, 0, N-1, x1-1, y1-1); Node cNode = tree.query(1, 0, N-1, y1, x2-2); Node rNode = tree.query(1, 0, N-1, x2-1, y2-1); cout << lNode.rMax + cNode.aSum + rNode.lMax << '\n'; } else { Node lNode = tree.query(1, 0, N-1, x1-1, x2-1); Node cNode = tree.query(1, 0, N-1, x2, y1-2); Node rNode = tree.query(1, 0, N-1, y1-1, y2-1); cout << max({ lNode.rMax + cNode.lMax, cNode.aMax, cNode.rMax + rNode.lMax, lNode.aSum + cNode.aSum + rNode.aSum }) << '\n'; } } return 0; }

제출 #165980

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: