fork(1) download
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <string>
  9. #include <queue>
  10. #include <stack>
  11. #include <algorithm>
  12. #include <cmath>
  13. #include <iomanip>
  14. #define dibs reserve
  15. #define OVER9000 1234567890
  16. #define patkan 9
  17. #define tisic 47
  18. #define soclose 1e-9
  19. #define pi 3.1415926535898
  20. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  21. #define chocolate win
  22. #define ff first
  23. #define ss second
  24. #define abs(x) ((x < 0)?-(x):(x))
  25. #define uint unsigned int
  26. #include <time.h>
  27. // mylittlepony
  28. using namespace std;
  29.  
  30. struct weed {
  31. int x,y,G;
  32.  
  33. bool operator<(const weed &A) const {
  34. return x < A.x;}
  35. };
  36.  
  37. struct node {
  38. int z,k;
  39. int son[2];
  40. int mod,val;};
  41.  
  42. struct intervalac {
  43. vector<node> T;
  44.  
  45. void constI(int akt) {
  46. node n =T[akt];
  47. if(n.z == n.k-1) return;
  48. for(int i =0; i < 2; i++) {
  49. if(i == 0) n.k =(n.k+n.z)/2;
  50. else {n.z =n.k; n.k =T[akt].k;}
  51. T[akt].son[i] =T.size();
  52. T.push_back(n);
  53. constI(T[akt].son[i]);}
  54. }
  55.  
  56. intervalac(int N) {
  57. T.dibs(2*N);
  58. node n;
  59. n.son[0] =n.son[1] =-1;
  60. n.val =n.mod =0;
  61. n.z =0, n.k =N;
  62. T.push_back(n);
  63. constI(0);}
  64.  
  65. void upd(int akt) {
  66. node n =T[akt];
  67. if(n.mod == 0) return;
  68. for(int i =0; i < 2; i++) if(n.son[i] != -1)
  69. T[n.son[i]].mod +=n.mod;
  70. T[akt].val +=n.mod;
  71. T[akt].mod =0;}
  72.  
  73. void add(int akt, int zac, int kon, int val) {
  74. // prirataj val k vsetkym prvkom [zac,kon)
  75. upd(akt);
  76. node n =T[akt];
  77. if(n.z >= kon || zac >= n.k) return;
  78. if(n.z == zac && n.k == kon) {
  79. T[akt].mod +=val;
  80. upd(akt);
  81. return;}
  82. add(n.son[0],zac,min(kon,T[n.son[0]].k),val);
  83. add(n.son[1],max(zac,T[n.son[1]].z),kon,val);
  84. upd(akt);
  85. T[akt].val =max(T[n.son[0]].val,T[n.son[1]].val);}
  86.  
  87. int get() {
  88. upd(0);
  89. return T[0].val;}
  90. };
  91.  
  92. int main() {
  93. freopen("lazy.in","r",stdin);
  94. freopen("lazy.out","w",stdout);
  95. int N,K;
  96. scanf(" %d %d",&N,&K);
  97. vector<weed> A(N);
  98. for(int i =0; i < N; i++) {
  99. int x,y;
  100. scanf(" %d %d %d",&A[i].G,&x,&y);
  101. A[i].x =x+y;
  102. A[i].y =x-y+1000000;}
  103. sort(A.begin(),A.end());
  104.  
  105. map<int,int> C;
  106. for(int i =0; i < N; i++) {
  107. C[A[i].y-K] =0;
  108. C[A[i].y+K] =0;}
  109. int a =0;
  110. for(map<int,int>::iterator it =C.begin(); it != C.end(); it++) it->ss =a++;
  111.  
  112. intervalac I(a+tisic);
  113. int ans =0, b =0;
  114.  
  115. for(int i =0; i < N; i++) {
  116. I.add(0,max(0,C[A[i].y-K]),min(a+patkan,C[A[i].y+K]+1),A[i].G);
  117. while(b < N && A[b].x < A[i].x-2*K) {
  118. I.add(0,max(0,C[A[b].y-K]),min(a+patkan,C[A[b].y+K]+1),-A[b].G);
  119. b++;}
  120. ans =max(ans,I.get());}
  121. printf("%d\n",ans);
  122. return 0;}
  123.  
  124. // look at my code
  125. // my code is amazing
  126.  
Success #stdin #stdout 0s 3444KB
stdin
Standard input is empty
stdout
Standard output is empty