fork download 
  1. #include<stdio.h>
  2.  
  3. long long min(long long a, long long b) { if (a < b)return a; return b; }
  4. long long max(long long a, long long b) { if (a > b)return a; return b; }
  5. long long F[2121212];
  6. long long tn;
  7. long long tree[2121212];
  8. long long search_g(long long ss, long long ee) {
  9. 	long long s = ss + tn;
  10. 	long long e = ee + tn;
  11. 	long long res = -1;
  12. 	while (s <= e) {
  13. 		if (s % 2 == 1)res = max(res, tree[s++]);
  14. 		if (e % 2 == 0)res = max(res, tree[e--]);
  15. 		s /= 2;
  16. 		e /= 2;
  17. 	}
  18. 	return res;
  19. }
  20. void insert_g(long long w, long long g) {
  21. 	long long i;
  22. 	for (i = tn + w; i > 0; i /= 2) {
  23. 		tree[i] = max(tree[i], g);
  24. 	}
  25. }
  26. int main() {
  27. 	long long n, m;
  28. 	long long i, j;
  29. 	long long ans = 1e18;
  30. 	scanf("%lld%lld", &n, &m);
  31. 	for (tn = 1; tn < n; tn *= 2);
  32. 	for (i = 1; i < tn * 2; i++)tree[i] = 0;
  33. 	for (i = 0; i < n; i++) {
  34. 		long long s;
  35. 		scanf("%lld%lld", &F[i], &s);
  36. 		insert_g(i, s);
  37. 	}
  38. 	long long S = 0;
  39. 	long long e = 0;
  40. 	for (i = 0; i < n; i++) {
  41. 		if (i > 0)S -= F[i];
  42. 		while (e<n&&S + F[e] < m)S += F[e++];
  43. 		if (e == n&&S < m)break;
  44. 		ans = min(ans, search_g(i, e - 1));
  45. 	}
  46. 	printf("%lld", ans);
  47. 	return 0;
  48. }
Success #stdin #stdout 0s 4388KB
comments (?)
stdin 
5 10
4 10
6 15
3 5
4 9
3 6
stdout 
9
https://ideone.com/CEGfrc
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!