fork(1) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sEexTE
USACO 2013/14 March
language:
C++ (gcc 8.3)
created:
10 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!