#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for (int i = 0; i < (n); i++) #define pb push_back #define st first #define nd second const int MAXN = 1 << 19; ll seg[2 * MAXN]; ll maks[MAXN]; pair<ll, int> T[MAXN]; void upd(int l, int r, ll x) { l += MAXN; r += MAXN; while (l < r) { if (l % 2 == 1) { seg[l] = max(seg[l], x); l++; } if (r % 2 == 0) { seg[r] = max(seg[r], x); r--; } l /= 2; r /= 2; } if (l == r) { seg[l] = max(seg[l], x); } } ll ans(int v) { v += MAXN; ll ile = 0; while (v > 0) { ile = max(ile, seg[v]); v /= 2; } return ile; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; ll c; cin >> n >> c; rep(i, n) { cin >> T[i].st >> T[i].nd; } int i = 0; while (i < n) { int j = i; vector<ll> odp; while (j < n && T[j].st == T[i].st) { // cout << "j = " << j << " maks = " << maks[j] << " ans = " << ans(j) - c << '\n'; odp.pb(max(maks[T[j].nd], ans(T[j].nd) - c)); j++; } j--; int sz = odp.size(); rep(it, sz) { int wzor = T[i + it].nd; maks[wzor] = max(maks[wzor], odp[it] + T[i + it].st); upd(0, wzor - 1, maks[wzor]); upd(wzor + 1, MAXN - 1, maks[wzor]); } i = j + 1; } ll wyn = 0; for (int i = 1; i < MAXN; i++) { wyn = max(wyn, maks[i]); } cout << wyn << '\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 | #include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for (int i = 0; i < (n); i++) #define pb push_back #define st first #define nd second const int MAXN = 1 << 19; ll seg[2 * MAXN]; ll maks[MAXN]; pair<ll, int> T[MAXN]; void upd(int l, int r, ll x) { l += MAXN; r += MAXN; while (l < r) { if (l % 2 == 1) { seg[l] = max(seg[l], x); l++; } if (r % 2 == 0) { seg[r] = max(seg[r], x); r--; } l /= 2; r /= 2; } if (l == r) { seg[l] = max(seg[l], x); } } ll ans(int v) { v += MAXN; ll ile = 0; while (v > 0) { ile = max(ile, seg[v]); v /= 2; } return ile; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; ll c; cin >> n >> c; rep(i, n) { cin >> T[i].st >> T[i].nd; } int i = 0; while (i < n) { int j = i; vector<ll> odp; while (j < n && T[j].st == T[i].st) { // cout << "j = " << j << " maks = " << maks[j] << " ans = " << ans(j) - c << '\n'; odp.pb(max(maks[T[j].nd], ans(T[j].nd) - c)); j++; } j--; int sz = odp.size(); rep(it, sz) { int wzor = T[i + it].nd; maks[wzor] = max(maks[wzor], odp[it] + T[i + it].st); upd(0, wzor - 1, maks[wzor]); upd(wzor + 1, MAXN - 1, maks[wzor]); } i = j + 1; } ll wyn = 0; for (int i = 1; i < MAXN; i++) { wyn = max(wyn, maks[i]); } cout << wyn << '\n'; return 0; } |