#include <algorithm> #include <bitset> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <string> #include <vector> using namespace std; #define PB push_back #define MP make_pair #define F first #define S second #define ALL(x) (x).begin(),(x).end() #define SIZE(x) (int)(x).size() #define CLEAR(tab) memset(tab, 0, sizeof(tab)) #define REP(x, n) for(int x = 0; x < (n); x++) #define FOR(x, b, e) for(int x = (b); x <= (e); x++) #define FORD(x, b, e) for(int x = (b); x >= (e); x--) #define VAR(v, n) __typeof(n) v = (n) #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define DEBUG(fmt, ...) fprintf(stderr, fmt, ##__VA_ARGS__) typedef long long int LL; typedef pair<int,int> PII; typedef vector<int> VI; const int MXN = 500010; const int C = 2 * 262144; const int INF = 1000000001; const int MOD = 1000000007; int n, c; int a[MXN], w[MXN]; LL tree[2 * C + 10]; void add(int x, LL val) { x += C; tree[x] = max(tree[x], val); x /= 2; while(x) { tree[x] = max(tree[2 * x], tree[2 * x + 1]); x /= 2; } } LL maks(int x) { x += C; LL res = 0; while(x) { if(x % 2) res = max(res, tree[x - 1]); else res = max(res, tree[x + 1]); x /= 2; } return res; } void test() { scanf("%d %d", &n, &c); FOR(i, 1, n) { scanf("%d %d", &a[i], &w[i]); } FOR(i, 1, n) { int iter = i; vector<pair<int, LL> > vec; while(iter <= n && a[i] == a[iter]) { LL res1 = maks(w[iter]) - c + a[iter]; LL res2 = tree[C + w[iter]] + a[iter]; vec.PB({w[iter], max(res1, res2)}); iter++; } FOREACH(it, vec) add(it -> F, it -> S); i = iter - 1; } printf("%lld\n", max(maks(1), tree[C + 1])); } int main() { int te = 1; //scanf("%d", &te); while(te--) test(); 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 | #include <algorithm> #include <bitset> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <string> #include <vector> using namespace std; #define PB push_back #define MP make_pair #define F first #define S second #define ALL(x) (x).begin(),(x).end() #define SIZE(x) (int)(x).size() #define CLEAR(tab) memset(tab, 0, sizeof(tab)) #define REP(x, n) for(int x = 0; x < (n); x++) #define FOR(x, b, e) for(int x = (b); x <= (e); x++) #define FORD(x, b, e) for(int x = (b); x >= (e); x--) #define VAR(v, n) __typeof(n) v = (n) #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define DEBUG(fmt, ...) fprintf(stderr, fmt, ##__VA_ARGS__) typedef long long int LL; typedef pair<int,int> PII; typedef vector<int> VI; const int MXN = 500010; const int C = 2 * 262144; const int INF = 1000000001; const int MOD = 1000000007; int n, c; int a[MXN], w[MXN]; LL tree[2 * C + 10]; void add(int x, LL val) { x += C; tree[x] = max(tree[x], val); x /= 2; while(x) { tree[x] = max(tree[2 * x], tree[2 * x + 1]); x /= 2; } } LL maks(int x) { x += C; LL res = 0; while(x) { if(x % 2) res = max(res, tree[x - 1]); else res = max(res, tree[x + 1]); x /= 2; } return res; } void test() { scanf("%d %d", &n, &c); FOR(i, 1, n) { scanf("%d %d", &a[i], &w[i]); } FOR(i, 1, n) { int iter = i; vector<pair<int, LL> > vec; while(iter <= n && a[i] == a[iter]) { LL res1 = maks(w[iter]) - c + a[iter]; LL res2 = tree[C + w[iter]] + a[iter]; vec.PB({w[iter], max(res1, res2)}); iter++; } FOREACH(it, vec) add(it -> F, it -> S); i = iter - 1; } printf("%lld\n", max(maks(1), tree[C + 1])); } int main() { int te = 1; //scanf("%d", &te); while(te--) test(); return 0; } |