fork download
  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
stdin
5 3
1 2 100
2 5 100
3 4 100
stdout
200