fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ii pair<int,int>
  4. #define p first
  5. #define k second
  6. const int N = 1e4;
  7. const int T = 3e4;
  8. int n, t = 0, res = 0;
  9. int st[T*4+5];
  10. ii a[N+5];
  11.  
  12. bool cmp(ii a, ii b){
  13. 	if(a.k != b.k) return a.k < b.k;
  14. 	return a.p < a.p;
  15. }
  16.  
  17. int get(int id, int l, int r, int u, int v){
  18. 	if(r < u || v < l) return 0;
  19. 	if(u <= l && r <= v) return st[id];
  20. 	int mid = (l+r) >> 1;
  21. 	return max(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
  22. }
  23.  
  24. void update(int id, int l, int r, int pos, int val){
  25. 	if(l == r){
  26. 		st[id] = max(st[id], val);
  27. 		return;
  28. 	}
  29. 	int mid = (l+r) >> 1;
  30. 	if(pos <= mid) update(id*2, l, mid, pos, val);
  31. 	else update(id*2+1, mid+1, r, pos, val);
  32. 	st[id] = max(st[id*2], st[id*2+1]);
  33. }
  34.  
  35. void checkTree(int id, int l, int r){
  36. 	if(l == r){
  37. 		cout << l << ' ' << r << ' ' << id << '\n';
  38. 		return;
  39. 	}
  40. 	int mid = (l+r) >> 1;
  41. 	checkTree(id*2, l, mid);
  42. 	checkTree(id*2+1, mid+1, r);
  43. 	cout << l << ' ' << r << ' ' << id << '\n';
  44. }
  45.  
  46. void solve(){
  47. 	cin >> n;
  48. 	for(int i = 1; i <= n; i++){
  49. 		cin >> a[i].p >> a[i].k;
  50. 		t = max(t, a[i].k);
  51. 	}
  52. 	sort(a+1, a+n+1, cmp);
  53. 	for(int i = 1; i <= n; i++){
  54. 		int preVal = get(1, 0, t, 0, a[i].p);
  55. 		int sum = preVal + a[i].k - a[i].p;
  56. 		res = max(res, sum);
  57. 		update(1, 0, t, a[i].k, sum);
  58. 	}
  59. 	cout << res;
  60. }
  61.  
  62. signed main(){
  63. 	ios_base::sync_with_stdio(0); cin.tie(0);
  64. 	// freopen("test.INP", "r", stdin);
  65. 	// freopen("test.OUT", "w", stdout);
  66. 	solve();
  67. 	return 0;
  68. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9fmrEr
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!