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