#include <bits/stdc++.h> #define int long long using namespace std; int n, c; const int MX = 5e5 + 9; vector<pair<int,int>>v; int tre[4*MX]; bool onstack[MX]; void update(int node, int start, int end, int tar, int val){ if(start == end) tre[node] = max(tre[node], val); else{ int mid = (start + end)>>1; if(mid >= tar){ update(node<<1, start, mid, tar, val); } else{ update((node<<1)+1, mid+1, end, tar, val); } tre[node] = max(tre[node<<1], tre[(node<<1)+1]); } } int query(int node, int L, int R, int start, int end){ if(start > R or end < L) return 0; else if(start >= L and end <= R) return tre[node]; else{ int mid = (start + end)>>1; return max(query(node<<1, L, R, start, mid), query((node<<1)+1, L, R, mid+1, end)); } } int32_t main(){ cin >> n >> c; for(int i = 0; i < n; ++i){ int a, w; cin >> a >> w; v.push_back({a, w}); } sort(v.begin(), v.end(), greater<pair<int,int>>()); int curh = v[0].first; queue<pair<int,int>>q; for(int i = 0; i < n; ++i){ int a = v[i].first, w = v[i].second; if(a < curh){ while(!q.empty()){ if(onstack[q.front().first]) update(1, 1, MX, q.front().first, q.front().second); onstack[q.front().first] = false; q.pop(); } } curh = a; if(onstack[w]) continue; onstack[w] = true; int val = a+query(1, w, w, 1, MX); val = max(val, a+query(1, 1, w-1, 1, MX)-c); val = max(val, a+query(1, w+1, MX, 1, MX)-c); q.push({w, val}); } while(!q.empty()){ if(onstack[q.front().first]) update(1, 1, MX, q.front().first, q.front().second); onstack[q.front().first] = false; q.pop(); } cout << query(1, 1, MX, 1, MX); }
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 | #include <bits/stdc++.h> #define int long long using namespace std; int n, c; const int MX = 5e5 + 9; vector<pair<int,int>>v; int tre[4*MX]; bool onstack[MX]; void update(int node, int start, int end, int tar, int val){ if(start == end) tre[node] = max(tre[node], val); else{ int mid = (start + end)>>1; if(mid >= tar){ update(node<<1, start, mid, tar, val); } else{ update((node<<1)+1, mid+1, end, tar, val); } tre[node] = max(tre[node<<1], tre[(node<<1)+1]); } } int query(int node, int L, int R, int start, int end){ if(start > R or end < L) return 0; else if(start >= L and end <= R) return tre[node]; else{ int mid = (start + end)>>1; return max(query(node<<1, L, R, start, mid), query((node<<1)+1, L, R, mid+1, end)); } } int32_t main(){ cin >> n >> c; for(int i = 0; i < n; ++i){ int a, w; cin >> a >> w; v.push_back({a, w}); } sort(v.begin(), v.end(), greater<pair<int,int>>()); int curh = v[0].first; queue<pair<int,int>>q; for(int i = 0; i < n; ++i){ int a = v[i].first, w = v[i].second; if(a < curh){ while(!q.empty()){ if(onstack[q.front().first]) update(1, 1, MX, q.front().first, q.front().second); onstack[q.front().first] = false; q.pop(); } } curh = a; if(onstack[w]) continue; onstack[w] = true; int val = a+query(1, w, w, 1, MX); val = max(val, a+query(1, 1, w-1, 1, MX)-c); val = max(val, a+query(1, w+1, MX, 1, MX)-c); q.push({w, val}); } while(!q.empty()){ if(onstack[q.front().first]) update(1, 1, MX, q.front().first, q.front().second); onstack[q.front().first] = false; q.pop(); } cout << query(1, 1, MX, 1, MX); } |