#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MINF = -1000000000000000000LL; // bardzo mała wartość struct Block { int a, w; }; struct Node { ll best, second; int best_pat; }; struct SegTree { int size; vector<Node> tree; SegTree(int n) { size = 1; while(size < n) size *= 2; tree.assign(2 * size, {MINF, MINF, 0}); } // Funkcja łącząca dwa węzły Node combine(const Node &L, const Node &R) { Node res; if(L.best > R.best) { res.best = L.best; res.best_pat = L.best_pat; res.second = max(L.second, R.best); } else if(L.best < R.best) { res.best = R.best; res.best_pat = R.best_pat; res.second = max(R.second, L.best); } else { res.best = L.best; // obie równe res.best_pat = L.best_pat; // dowolnie res.second = max(L.second, R.second); } return res; } // Aktualizacja pozycji idx (1-indexowane dla a) void update(int idx, ll val, int pat) { idx += size - 1; // Aktualizujemy, jeśli nowe dp jest większe if(val > tree[idx].best) { tree[idx].best = val; tree[idx].best_pat = pat; } // Przechodzimy do góry drzewa for(idx /= 2; idx >= 1; idx /= 2) { tree[idx] = combine(tree[2*idx], tree[2*idx+1]); } } // Zapytanie w przedziale [l, r] (1-indexowane) Node query(int l, int r) { Node resL = {MINF, MINF, 0}, resR = {MINF, MINF, 0}; l += size - 1; r += size - 1; while(l <= r) { if(l % 2 == 1) { resL = combine(resL, tree[l]); l++; } if(r % 2 == 0) { resR = combine(tree[r], resR); r--; } l /= 2; r /= 2; } return combine(resL, resR); } }; /// Struktura do zapytań per-wzór. /// Dla każdego wzoru będziemy trzymać wektor par (a, prefix_max) using Vec = vector<pair<int, ll>>; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, c; cin >> n >> c; vector<Block> blocks(n); for (int i = 0; i < n; i++){ cin >> blocks[i].a >> blocks[i].w; } // Bloki są podane w kolejności niemalejącej – odwracamy, aby uzyskać malejący ciąg według a. reverse(blocks.begin(), blocks.end()); // Maksymalna wartość a (zakres [1, MAXA]) int MAXA = 500000; // Globalna struktura – segment tree – dla przedziałowych zapytań wg wartości a. SegTree seg(MAXA); // Struktury per-wzór: mapa wzoru -> wektor (a, prefix_max_dp) unordered_map<int, Vec> patMap; patMap.reserve(n*2); vector<ll> dp(n, 0); ll ans = 0; // Przetwarzamy bloki w kolejności: dla i od n-1 do 0. // Dzięki temu, dla danego bloku, już obliczone są dp dla bloków "wyżej" (mniejszych a). for (int i = n - 1; i >= 0; i--) { int a = blocks[i].a; int w = blocks[i].w; // Zapytanie w globalnym segtree dla przedziału [1, a-1] ll candidate_diff = MINF; if(a > 1) { Node node = seg.query(1, a - 1); // Jeśli najlepszy wynik globalny pochodzi z tego samego wzoru, używamy drugiego najlepszego. if(node.best_pat == w) candidate_diff = node.second - c; else candidate_diff = node.best - c; } // Zapytanie w strukturze dla wzoru w – binary search w wektorze (jeśli już istnieją klocki tego wzoru) ll candidate_same = MINF; if(patMap.find(w) != patMap.end()){ Vec &vec = patMap[w]; // Znajdź ostatni element z a < current a. auto it = std::lower_bound(vec.begin(), vec.end(), make_pair(a, (ll) -1), [](const pair<int,ll> &p, const pair<int,ll> &q) { return p.first < q.first; }); if(it != vec.begin()){ it--; candidate_same = it->second; } } ll candidate = max(candidate_same, candidate_diff); if(candidate < 0) candidate = 0; dp[i] = a + candidate; ans = max(ans, dp[i]); // Aktualizacja globalnego segment tree: w pozycji a przechowujemy maksymalne dp dla danego a. seg.update(a, dp[i], w); // Aktualizacja struktury per-wzór: dodajemy parę (a, nowy prefix_max) { Vec &vec = patMap[w]; // operator [] utworzy wektor, jeśli nie istniał ll newVal = dp[i]; if(!vec.empty()) newVal = max(newVal, vec.back().second); vec.push_back({a, newVal}); } } cout << ans << "\n"; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 | #include <bits/stdc++.h> using namespace std; using ll = long long; const ll MINF = -1000000000000000000LL; // bardzo mała wartość struct Block { int a, w; }; struct Node { ll best, second; int best_pat; }; struct SegTree { int size; vector<Node> tree; SegTree(int n) { size = 1; while(size < n) size *= 2; tree.assign(2 * size, {MINF, MINF, 0}); } // Funkcja łącząca dwa węzły Node combine(const Node &L, const Node &R) { Node res; if(L.best > R.best) { res.best = L.best; res.best_pat = L.best_pat; res.second = max(L.second, R.best); } else if(L.best < R.best) { res.best = R.best; res.best_pat = R.best_pat; res.second = max(R.second, L.best); } else { res.best = L.best; // obie równe res.best_pat = L.best_pat; // dowolnie res.second = max(L.second, R.second); } return res; } // Aktualizacja pozycji idx (1-indexowane dla a) void update(int idx, ll val, int pat) { idx += size - 1; // Aktualizujemy, jeśli nowe dp jest większe if(val > tree[idx].best) { tree[idx].best = val; tree[idx].best_pat = pat; } // Przechodzimy do góry drzewa for(idx /= 2; idx >= 1; idx /= 2) { tree[idx] = combine(tree[2*idx], tree[2*idx+1]); } } // Zapytanie w przedziale [l, r] (1-indexowane) Node query(int l, int r) { Node resL = {MINF, MINF, 0}, resR = {MINF, MINF, 0}; l += size - 1; r += size - 1; while(l <= r) { if(l % 2 == 1) { resL = combine(resL, tree[l]); l++; } if(r % 2 == 0) { resR = combine(tree[r], resR); r--; } l /= 2; r /= 2; } return combine(resL, resR); } }; /// Struktura do zapytań per-wzór. /// Dla każdego wzoru będziemy trzymać wektor par (a, prefix_max) using Vec = vector<pair<int, ll>>; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, c; cin >> n >> c; vector<Block> blocks(n); for (int i = 0; i < n; i++){ cin >> blocks[i].a >> blocks[i].w; } // Bloki są podane w kolejności niemalejącej – odwracamy, aby uzyskać malejący ciąg według a. reverse(blocks.begin(), blocks.end()); // Maksymalna wartość a (zakres [1, MAXA]) int MAXA = 500000; // Globalna struktura – segment tree – dla przedziałowych zapytań wg wartości a. SegTree seg(MAXA); // Struktury per-wzór: mapa wzoru -> wektor (a, prefix_max_dp) unordered_map<int, Vec> patMap; patMap.reserve(n*2); vector<ll> dp(n, 0); ll ans = 0; // Przetwarzamy bloki w kolejności: dla i od n-1 do 0. // Dzięki temu, dla danego bloku, już obliczone są dp dla bloków "wyżej" (mniejszych a). for (int i = n - 1; i >= 0; i--) { int a = blocks[i].a; int w = blocks[i].w; // Zapytanie w globalnym segtree dla przedziału [1, a-1] ll candidate_diff = MINF; if(a > 1) { Node node = seg.query(1, a - 1); // Jeśli najlepszy wynik globalny pochodzi z tego samego wzoru, używamy drugiego najlepszego. if(node.best_pat == w) candidate_diff = node.second - c; else candidate_diff = node.best - c; } // Zapytanie w strukturze dla wzoru w – binary search w wektorze (jeśli już istnieją klocki tego wzoru) ll candidate_same = MINF; if(patMap.find(w) != patMap.end()){ Vec &vec = patMap[w]; // Znajdź ostatni element z a < current a. auto it = std::lower_bound(vec.begin(), vec.end(), make_pair(a, (ll) -1), [](const pair<int,ll> &p, const pair<int,ll> &q) { return p.first < q.first; }); if(it != vec.begin()){ it--; candidate_same = it->second; } } ll candidate = max(candidate_same, candidate_diff); if(candidate < 0) candidate = 0; dp[i] = a + candidate; ans = max(ans, dp[i]); // Aktualizacja globalnego segment tree: w pozycji a przechowujemy maksymalne dp dla danego a. seg.update(a, dp[i], w); // Aktualizacja struktury per-wzór: dodajemy parę (a, nowy prefix_max) { Vec &vec = patMap[w]; // operator [] utworzy wektor, jeśli nie istniał ll newVal = dp[i]; if(!vec.empty()) newVal = max(newVal, vec.back().second); vec.push_back({a, newVal}); } } cout << ans << "\n"; return 0; } |