fork(1) download
copy 
  1. import java.util.Scanner;
  2.  
  3. class ALGOCRUSH {
  4. 	public static void main(String[] args) {
  5. 		Scanner s = new Scanner(System.in);
  6. 		int n = s.nextInt(), q = s.nextInt(), temp = n;
  7. 		long[] tree, lazy;
  8. 		if (((n) & (n - 1)) == 0) {
  9. 			tree = new long[2 * n - 1];
  10. 			lazy = new long[2 * n - 1];
  11. 		} else {
  12. 			n = (int) (Math.log(n) / Math.log(2));
  13. 			n++;
  14. 			n = 1 << n;
  15. 			tree = new long[2 * n - 1];
  16. 			lazy = new long[2 * n - 1];
  17. 		}
  18. 		while (q-- > 0) {
  19. 			int l = s.nextInt(), r = s.nextInt(), val = s.nextInt();
  20. 			update(tree, lazy, l - 1, r - 1, 0, temp - 1, 0, val);
  21. 		}
  22. 		System.out.println(rmq(tree, lazy, 0, temp - 1, 0, temp - 1, 0));
  23. 	}
  24.  
  25. 	static void update(long[] tree, long[] lazy, int qlow, int qhigh, int low, int high, int pos, int val) {
  26. 		if (low > high)
  27. 			return;
  28. 		if (lazy[pos] != 0) {
  29. 			tree[pos] += lazy[pos];
  30. 			if (low != high) {
  31. 				lazy[2 * pos + 1] += lazy[pos];
  32. 				lazy[2 * pos + 2] += lazy[pos];
  33. 			}
  34. 			lazy[pos] = 0;
  35. 		}
  36. 		if (qlow > high || qhigh < low)
  37. 			return;
  38. 		if (qlow <= low && qhigh >= high) {
  39. 			tree[pos] += val;
  40. 			if (low != high) {
  41. 				lazy[2 * pos + 1] += val;
  42. 				lazy[2 * pos + 2] += val;
  43. 			}
  44. 			return;
  45. 		}
  46. 		int mid = (low + high) >> 1;
  47. 		update(tree, lazy, qlow, qhigh, low, mid, 2 * pos + 1, val);
  48. 		update(tree, lazy, qlow, qhigh, mid + 1, high, 2 * pos + 2, val);
  49. 		tree[pos] = Math.max(tree[2 * pos + 1], tree[2 * pos + 2]);
  50. 	}
  51.  
  52. 	static long rmq(long[] tree, long[] lazy, int qlow, int qhigh, int low, int high, int pos) {
  53. 		if (low > high)
  54. 			return Integer.MIN_VALUE;
  55. 		if (lazy[pos] != 0) {
  56. 			tree[pos] += lazy[pos];
  57. 			if (low != high) {
  58. 				lazy[2 * pos + 1] += lazy[pos];
  59. 				lazy[2 * pos + 2] += lazy[pos];
  60. 			}
  61. 			lazy[pos] = 0;
  62. 		}
  63. 		if (qlow > high || qhigh < low) {
  64. 			return Integer.MIN_VALUE;
  65. 		}
  66. 		if (qlow <= low && qhigh >= high) {
  67. 			return tree[pos];
  68. 		}
  69. 		int mid = (low + high) >> 1;
  70. 		return Math.max(rmq(tree, lazy, qlow, qhigh, low, mid, 2 * pos + 1),
  71. 				rmq(tree, lazy, qlow, qhigh, mid + 1, high, 2 * pos + 1));
  72.  
  73. 	}
  74.  
  75. }
Success #stdin #stdout 0.05s 4386816KB
comments (?)
stdin
copy 
5 3
1 2 100
2 5 100
3 4 100
stdout
copy 
200
https://ideone.com/DzZlW7
language:
Java (HotSpot 12)
created:
7 years 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!