제출 #1190560

#제출 시각아이디문제언어결과실행 시간메모리
1190560tch1cherinAnts and Sugar (JOI22_sugar)C++20
100 / 100
3741 ms313460 KiB
#include <bits/stdc++.h> using namespace std; constexpr long long INF = 1e18; void chmax(long long& a, long long b) { a = a > b ? a : b; } struct segment_tree { struct node { long long DP[2][2], DP_small[2][2][3]; long long alt_tag = 0, small_tag = 0; node() { for (int x = 0; x < 2; x++) { for (int y = 0; y < 2; y++) { if (x == y) { DP[x][y] = 0; for (int z = 0; z < 3; z++) { DP_small[x][y][z] = 0; } } else { DP[x][y] = -INF; for (int z = 0; z < 3; z++) { DP_small[x][y][z] = -INF; } } } } } }; node merge(node a, node b) { node result; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { result.DP[i][k] = max(result.DP[i][k], a.DP[i][j] + b.DP[j][k]); for (int na = 0; na < 3; na++) { for (int nb = 0; na + nb < 3; nb++) { chmax(result.DP_small[i][k][na + nb], a.DP_small[i][j][na] + b.DP_small[j][k][nb]); } } } } } return result; } int size; vector<node> tree; segment_tree(int n) { size = 1; while (size < n) { size *= 2; } node neutral; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { neutral.DP[i][j] = 0; for (int cnt = 0; cnt < 3; cnt++) { neutral.DP_small[i][j][cnt] = (cnt == int(i == 1 && j == 0) ? 0 : -INF); } } } tree.assign(size * 2, neutral); for (int i = size - 1; i > 0; i--) { tree[i] = merge(tree[i * 2], tree[i * 2 + 1]); } } void alt_apply(int x, long long value) { for (int i = 0; i < 2; i++) { tree[x].DP[i][i ^ 1] += value * (i == 0 ? -1 : +1); for (int n = 0; n < 3; n++) { tree[x].DP_small[i][i ^ 1][n] += value * (i == 0 ? -1 : +1); } } tree[x].alt_tag += value; } void small_apply(int x, long long value) { for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { for (int n = 0; n < 3; n++) { tree[x].DP_small[i][j][n] += n * value; } } } for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { tree[x].DP[i][j] = -INF; for (int n = 0; n < 3; n++) { tree[x].DP[i][j] = max(tree[x].DP[i][j], tree[x].DP_small[i][j][n]); } } } tree[x].small_tag += value; } void propagate(int x) { if (tree[x].alt_tag != 0) { alt_apply(x * 2, tree[x].alt_tag); alt_apply(x * 2 + 1, tree[x].alt_tag); tree[x].alt_tag = 0; } if (tree[x].small_tag != 0) { small_apply(x * 2, tree[x].small_tag); small_apply(x * 2 + 1, tree[x].small_tag); tree[x].small_tag = 0; } } void alt_update(int l, int r, int value, int x, int lx, int rx) { if (lx >= r || rx <= l) { return; } else if (lx >= l && rx <= r) { alt_apply(x, value); } else { propagate(x); int mid = (lx + rx) / 2; alt_update(l, r, value, x * 2, lx, mid); alt_update(l, r, value, x * 2 + 1, mid, rx); tree[x] = merge(tree[x * 2], tree[x * 2 + 1]); } } void alt_update(int l, int r, int value) { alt_update(l, r, value, 1, 0, size); } void small_update(int l, int r, int value, int x, int lx, int rx) { if (lx >= r || rx <= l) { return; } else if (lx >= l && rx <= r) { small_apply(x, value); } else { propagate(x); int mid = (lx + rx) / 2; small_update(l, r, value, x * 2, lx, mid); small_update(l, r, value, x * 2 + 1, mid, rx); tree[x] = merge(tree[x * 2], tree[x * 2 + 1]); } } void small_update(int l, int r, int value) { small_update(l, r, value, 1, 0, size); } pair<node, bool> query(int l, int r, int x, int lx, int rx) { if (lx >= r || rx <= l) { return {{}, false}; } else if (lx >= l && rx <= r) { return {tree[x], true}; } else { propagate(x); int mid = (lx + rx) / 2; auto [left_node, left_exists] = query(l, r, x * 2, lx, mid); auto [right_node, right_exists] = query(l, r, x * 2 + 1, mid, rx); if (left_exists && right_exists) { return {merge(left_node, right_node), true}; } else if (left_exists) { return {left_node, true}; } else { return {right_node, true}; } } } long long query(int l, int r) { return query(l, r, 1, 0, size).first.DP[0][0]; } }; int main() { cin.tie(nullptr)->sync_with_stdio(false); int Q, L; cin >> Q >> L; vector<int> T(Q), X(Q), A(Q); for (int i = 0; i < Q; i++) { cin >> T[i] >> X[i] >> A[i]; } vector<int> diff; for (int i = 0; i < Q; i++) { diff.push_back(X[i]); diff.push_back(X[i] + 1); } sort(diff.begin(), diff.end()); diff.resize(unique(diff.begin(), diff.end()) - diff.begin()); int K = int(diff.size()); segment_tree DS(K); long long ants = 0; for (int i = 0; i < Q; i++) { if (T[i] == 1) { int pos = upper_bound(diff.begin(), diff.end(), X[i]) - diff.begin(); DS.alt_update(pos, K, A[i]); ants += A[i]; } else { int lpos = upper_bound(diff.begin(), diff.end(), X[i] - L) - diff.begin(); int rpos = upper_bound(diff.begin(), diff.end(), X[i] + L) - diff.begin(); DS.small_update(lpos, rpos, -A[i]); DS.alt_update(rpos, K, -A[i]); } cout << ants - DS.query(0, K) << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...