fork download
copy 
  1. /***********************************************************
  2. 	When you are inspired by passion 
  3. 	and you want to live for the current moment
  4.  
  5. 	When your every thought and action
  6. 	has the power to become the story of your future
  7.  
  8. 	When difficulties stand to demolish your Glory
  9. 	Just remember that Life is a 'Golden adverse Story'
  10.  
  11. 	Withstand it to acheive your passion and dreams
  12. 	more amazingly more easily.
  13.  
  14. 	Why then? When writing the story of your Life
  15. 	You want to Let someone else hold your pen
  16.  
  17. 					huzaifa242©
  18.  
  19. ***********************************************************/
  20. #include <bits/stdc++.h>
  21. using namespace std;
  22. //#define int int64_t use for 64-bit integers
  23. #define int int32_t //use for 32-bit integers
  24. #define MAX 100005
  25. #define x first 
  26. #define y second
  27.  
  28. //for 64-bit change 1e9 to 1e18
  29. const int inf=1e9;
  30.  
  31. int seed;
  32. mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
  33. inline int rnd(int l=0,int r=INT_MAX)
  34. {return uniform_int_distribution<int>(l,r)(rng);}
  35.  
  36. template <typename T,typename G>
  37. ostream& operator << (ostream& out, const pair<T,G> &a) 
  38. {return out<<"("<<a.x<<" , "<<a.y<<")";}
  39.  
  40. template <typename T>
  41. ostream& operator << (ostream& out, const vector<T> &a) 
  42. {out<<"[";for(const auto &i:a)out<<i<<" , ";return out<<"]"<<endl;}
  43.  
  44. template <typename T>
  45. ostream& operator << (ostream& out, const set<T> &a) 
  46. {out<<"{";for(const auto &i:a)out<<i<<" , ";return out<<"}"<<endl;}
  47.  
  48. template <typename T,typename G>
  49. ostream& operator << (ostream& out, const map<T,G> &a) 
  50. {out<<"<";for(const auto &i:a)out<<i<<" , ";return out<<">"<<endl;}
  51.  
  52. template<typename T, size_t N>
  53. typename enable_if<!is_same<typename remove_cv<T>::type, char>::value,
  54. ostream&>::type operator<<(ostream& out, T(&a)[N])
  55. {out<<'[';for(size_t i=0;i<N;++i)out<<a[i]<<" , ";out <<"]"<<endl;return out;}
  56.  
  57. class ConvexHull_trick_Semi{
  58. 	private:
  59. 	class line{
  60. 		private:
  61. 		int m,c;
  62. 		long double xlft;
  63. 		public:
  64. 		explicit line(int _m=0,int _c=0){
  65. 			m=_m;
  66. 			c=_c;
  67. 			xlft=-inf;
  68. 		}
  69. 		int getc() const
  70. 		{ return c; }
  71. 		int getm() const 
  72. 		{ return m; }
  73. 		void setxlft(long double lf)
  74. 		{ xlft=lf; }
  75. 		long double getxlft() const
  76. 		{ return xlft; }
  77. 		int gety( int x) const 
  78. 		{ return m*x +c; }
  79. 		bool isparallel(line ll) const
  80. 		{ return m==ll.m; }
  81. 		long double intersectX(line ll) const 
  82. 		{ return isparallel(ll)?inf:(1.0*(c-ll.c))/(ll.m-m); }
  83. 	};
  84. 	bool maxQ;
  85. 	public:
  86. 	vector<line> hull;
  87. 	ConvexHull_trick_Semi(){}
  88. 	ConvexHull_trick_Semi(bool mq){
  89. 		maxQ=mq;
  90. 	}
  91. 	bool useless(line l1, line l2, line l3)
  92. 	{ return l1.intersectX(l3) <= l1.intersectX(l2); }
  93. 	void addline(int m,int c){
  94. 		line ll;
  95. 		if(maxQ)
  96. 			ll=line(-m,-c);
  97. 		else
  98. 			ll=line(m,c);
  99. 		while(hull.size()>=2 && useless(hull[hull.size()-2],hull[hull.size()-1],ll))
  100. 			hull.pop_back();
  101. 		if(hull.size()){
  102. 			long double dst=hull.back().intersectX(ll); 
  103. 			ll.setxlft(dst);
  104. 		}
  105. 		hull.push_back(ll);
  106. 	}
  107. 	int query(int x){
  108. 		int ll=0,rr=hull.size()-1,mm,aa=0;
  109. 		while(ll<=rr){
  110. 			mm=(ll+rr)/2;
  111. 			if(hull[mm].getxlft()<= (1.0 * x)){
  112. 				aa=mm;
  113. 				ll=mm+1;
  114. 			}else
  115. 				rr=mm-1;
  116. 		}
  117. 		return (maxQ?-hull[aa].gety(x):hull[aa].gety(x));
  118. 	}
  119. };
  120.  
  121. /*  It is assumed that B can take positive and negative values
  122. 	If is non-negative change implementation of query in 
  123. 	convexhulltrick class.
  124. */
  125.  
  126. //each bucket stores a convex hull, lazy b, and lazy constant a-L*b
  127.  
  128. struct bkt{
  129. 	ConvexHull_trick_Semi poly;
  130. 	int b,c;
  131. };
  132. class sqrt_decomposition{
  133. 	private:
  134. 	int bksz,tbk,n;
  135. 	//sqan is the array of buckets
  136. 	vector<bkt> sqan;
  137. 	//vals is the actual array on which we are operating
  138. 	vector<int> vals;
  139. 	public:
  140. 	sqrt_decomposition(int size){
  141. 		n=size;
  142. 		bksz=sqrt(n);
  143. 		tbk=(n%bksz==0?n/bksz:(n/bksz)+1);
  144. 		sqan.resize(tbk);
  145. 		vals.assign(n,0);
  146. 	}
  147. 	void sqan_init(){
  148. 		int i;
  149. 		for(i=0;i<tbk;i++){
  150. 			sqan[i].poly=ConvexHull_trick_Semi(true);
  151. 			sqan[i].b=0;
  152. 			sqan[i].c=0;
  153. 		}
  154. 		for(i=0;i<n;i++){
  155. 			sqan[i/bksz].poly.addline(i+1,vals[i]);
  156. 		}
  157. 	}
  158. 	void update(int l, int r, int a, int b){
  159. 		int fix=a-(l+1)*b;
  160. 		int i,bs,be,ans,s,e;
  161. 		bs=(l)/bksz+1;
  162. 		be=(r)/bksz;
  163. 		s=((l)/bksz)*bksz;
  164. 		//l to starting of first bucket
  165. 		sqan[bs-1].poly.hull.clear();
  166. 		for(i=s;i<bs*bksz;i++){
  167. 			vals[i]+=(sqan[bs-1].c + (i+1)*sqan[bs-1].b);
  168. 			sqan[bs-1].c=0;
  169. 			sqan[bs-1].b=0;
  170. 			if(i<l){
  171. 				sqan[bs-1].poly.addline(i+1,vals[i]);
  172. 			}else{
  173. 				vals[i]+=a+(i-l)*b;
  174. 				sqan[bs-1].poly.addline(i+1,vals[i]);
  175. 			}
  176. 		}
  177. 		//all the bucket jumps
  178. 		for(i=bs;i<be;i++){
  179. 			sqan[i].b+=b;
  180. 			sqan[i].c+=fix; 
  181. 		}
  182. 		e=min((be+1)*bksz,n);
  183. 		//last bucket to r
  184. 		sqan[be].poly.hull.clear();
  185. 		for(i=be*bksz;i<e;i++){
  186. 			vals[i]+=(sqan[be].c + (i+1)*sqan[be].b);
  187. 			sqan[be].c=0;
  188. 			sqan[be].b=0;
  189. 			if(i<=r){
  190. 				vals[i]+=a+(i-l)*b;
  191. 				sqan[be].poly.addline(i+1,vals[i]);
  192. 			}else{
  193. 				sqan[be].poly.addline(i+1,vals[i]);
  194. 			}
  195. 		}
  196. 	}
  197. 	int query(int l,int r){
  198. 		int i,bs,be,ans=INT_MIN,s,e;
  199. 		bs=(l)/bksz+1;
  200. 		be=(r)/bksz;
  201. 		s=((l)/bksz)*bksz;
  202. 		for(i=l;i<=min(bs*bksz-1,r);i++){
  203. 			ans=max(ans,(i+1)*sqan[bs-1].b + vals[i] + sqan[bs-1].c);
  204. 		}
  205. 		for(i=bs;i<be;i++){
  206. 			ans=max(ans,sqan[i].poly.query(sqan[i].b) + sqan[i].c);
  207. 		}
  208. 		e=min((be+1)*bksz,n);
  209. 		for(i=max(be*bksz,l);i<=r;i++){
  210. 			ans=max(ans,(i+1)*sqan[be].b + vals[i] + sqan[be].c);
  211. 		}
  212. 		return ans;     
  213. 	}
  214. };
  215.  
  216. signed main(){
  217. 	ios_base::sync_with_stdio(false);
  218. 	cin.tie(NULL);cout.tie(NULL);
  219. 	#ifndef ONLINE_JUDGE
  220. 		freopen("input.txt","r",stdin);
  221. 		freopen("output.txt","w",stdout);  
  222. 	#endif
  223. 	int n,q;
  224. 	cin>>n>>q;
  225. 	sqrt_decomposition sq(n);
  226. 	sq.sqan_init();
  227. 	while(q--){
  228. 		int c;
  229. 		cin>>c;
  230. 		if(c==1){
  231. 			int l,r,a,b;
  232. 			cin>>l>>r>>a>>b;
  233. 			sq.update(l-1,r-1,a,b);
  234. 		}else{
  235. 			int l,r;
  236. 			cin>>l>>r;
  237. 			int ans=sq.query(l-1,r-1);
  238. 			cout<<ans<<"\n";
  239. 		}
  240. 	}
  241. 	return 0;
  242. }
  243.  
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
5 7
1 2 4 1 1
2 1 1
2 2 2
2 3 3
2 4 4
2 5 5
2 1 3
stdout
copy 
0
1
2
3
0
2
https://ideone.com/TJH8cE
language:
C++14 (gcc 8.3)
created:
4 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!