fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i,a,b) for(int i=a;i<b;i++)
  4. #define REP(i,b) FOR(i,0,b)
  5. #define PB push_back
  6. #define MP make_pair
  7.  
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11. typedef pair<int,int> pii;
  12.  
  13. int read(){
  14. 	int i;
  15. 	scanf("%d",&i);
  16. 	return i;
  17. }
  18.  
  19. const int maxN=200000;
  20.  
  21. struct Pos{
  22. 	int x,y;
  23. 	bool operator<(const Pos& rhs)const{
  24. 		if(x!=rhs.x)
  25. 			return x<rhs.x;
  26. 		else
  27. 			return y>rhs.y;
  28. 	}
  29. 	bool operator==(const Pos& rhs)const{
  30. 		return x==rhs.x&&y==rhs.y;
  31. 	}
  32. } none=Pos{-1,-1};
  33.  
  34. ll Rect(const Pos& tl,const Pos& br){
  35. 	return ll(tl.y-br.y)*(br.x-tl.x);
  36. }
  37.  
  38. struct Query{
  39. 	Pos p;
  40. 	int i;
  41. 	bool operator<(const Query& rhs)const{
  42. 		return p<rhs.p;
  43. 	}
  44. };
  45.  
  46. struct RectSeg{
  47. 	Pos d[1<<19][4];
  48. 	int s;
  49. 	void Init(int n){
  50. 		s=1;
  51. 		while(s<n)s*=2;
  52. 		fill(d[0],d[s*2],none);
  53. 	}
  54. 	void Update(int i,Pos p){
  55. 		i+=s;
  56. 		fill(d[i],d[i]+4,p);
  57. 		while((i/=2)>=1){
  58. 			d[i][0]=d[i*2][0];
  59. 			d[i][1]=d[i*2][3];
  60. 			d[i][2]=d[i*2+1][0];
  61. 			d[i][3]=d[i*2+1][3];
  62. 			if(d[i][0]==none)
  63. 				d[i][0]=d[i][2];
  64. 			if(d[i][3]==none)
  65. 				d[i][3]=d[i][1];
  66. 		}
  67. 	}
  68. 	ll GetMax(Pos p){
  69. 		if(d[1][1]==none&&d[1][2]==none)
  70. 			return 0;
  71. 		int i=1;
  72. 		while(i<s){
  73. 			if(d[i][1]==none)
  74. 				i=i*2+1;
  75. 			else if(d[i][2]==none)
  76. 				i=i*2;
  77. 			else if(Rect(d[i][1],p)>Rect(d[i][2],p))
  78. 				i=i*2;
  79. 			else
  80. 				i=i*2+1;
  81. 		}
  82. 		return Rect(d[i][0],p);
  83. 	}
  84. } rectSeg;
  85.  
  86. ll ans[maxN];
  87. struct Solver{
  88. 	Pos convex[maxN];
  89. 	int pr[maxN],nx[maxN];
  90. 	void Connect(int a,int b){
  91. 		if(a!=-1)nx[a]=b;
  92. 		if(b!=-1)pr[b]=a;
  93. 	}
  94. 	vector<int> del[maxN];
  95. 	Query qs[maxN];
  96. 	void ComputeY(const Pos& a,const Pos& b,int x,ll& d,ll& e,ll& f){
  97. 		ll p=ll(b.y-a.y)*(x-a.x);
  98. 		e=b.x-a.x;
  99. 		ll q=p/e;
  100. 		d=b.y-q;
  101. 		f=p-q*e;
  102. 	}
  103. 	void AddDel(int b,int u,int v){
  104. 		if(b==-1)
  105. 			return;
  106. 		int a=pr[b],c=nx[b];
  107. 		if(a==-1||c==-1)
  108. 			return;
  109. 		int l=u-1,r=v;
  110. 		while(r-l>1){
  111. 			int m=(l+r)/2;
  112. 			ll d,e,f,D,E,F;
  113. 			ComputeY(convex[a],convex[b],qs[m].p.x,d,e,f);
  114. 			ComputeY(convex[b],convex[c],qs[m].p.x,D,E,F);
  115. 			if(d!=D){
  116. 				if(d<D)
  117. 					l=m;
  118. 				else
  119. 					r=m;
  120. 			}else if(f*E>F*e)
  121. 				l=m;
  122. 			else
  123. 				r=m;
  124. 		}
  125. 		if(r<v)
  126. 			del[r].PB(b);
  127. 	}
  128. 	void Solve(vector<Pos>& ps,const vector<Query>& _qs){
  129. 		int s=0,lastX=-1,lastY=-1,q=_qs.size();
  130. 		copy(_qs.begin(),_qs.end(),qs);
  131. 		sort(ps.begin(),ps.end());
  132. 		for(auto&& p:ps)
  133. 			if(lastX<p.x&&lastY<p.y){
  134. 				convex[s++]=p;
  135. 				qs[q++]=Query{p,-1};
  136. 				lastX=p.x;
  137. 				lastY=p.y;
  138. 			}
  139.  
  140. 		fill(pr,pr+s,-1);
  141. 		fill(nx,nx+s,-1);
  142. 		rectSeg.Init(s);
  143. 		sort(qs,qs+q);
  144. 		REP(i,q)
  145. 			del[i].clear();
  146. 		int k=0;
  147. 		REP(i,q){
  148. 			for(int j=0;j<(int)del[i].size();j++){
  149. 				int d=del[i][j];
  150. 				if(pr[d]==-1&&nx[d]==-1)
  151. 					continue;
  152. 				Connect(pr[d],nx[d]);
  153. 				rectSeg.Update(d,none);
  154. 				AddDel(pr[d],i,q);
  155. 				AddDel(nx[d],i,q);
  156. 				pr[d]=nx[d]=-1;
  157. 			}
  158. 			if(qs[i].i==-1){
  159. 				rectSeg.Update(k,qs[i].p);
  160. 				Connect(k-1,k);
  161. 				AddDel(k-1,i+1,q);
  162. 				k++;
  163. 			}else
  164. 				ans[qs[i].i]=max(ans[qs[i].i],rectSeg.GetMax(qs[i].p));
  165. 		}
  166. 	}
  167. } solver;
  168.  
  169. struct QuerySeg{
  170. 	vector<Pos> ps[1<<19];
  171. 	vector<Query> qs[1<<19];
  172. 	int s;
  173. 	void Init(int n){
  174. 		s=1;
  175. 		while(s<n)s*=2;
  176. 	}
  177. 	void AddPos(int b,int e,int l,int r,Pos p,int i){
  178. 		if(e<=l||r<=b)
  179. 			return;
  180. 		if(b<=l&&r<=e){
  181. 			ps[i].PB(p);
  182. 			return;
  183. 		}
  184. 		AddPos(b,e,l,(l+r)/2,p,i*2);
  185. 		AddPos(b,e,(l+r)/2,r,p,i*2+1);
  186. 	}
  187. 	void AddPos(int b,int e,Pos p){
  188. 		if(b<e)
  189. 			AddPos(b,e,0,s,p,1);
  190. 	}
  191. 	void AddQuery(int i,Query q){
  192. 		i+=s;
  193. 		while(i>=1){
  194. 			qs[i].PB(q);
  195. 			i/=2;
  196. 		}
  197. 	}
  198. 	void SolveAll(){
  199. 		FOR(i,1,s*2)
  200. 			if(!ps[i].empty()&&!qs[i].empty())
  201. 				solver.Solve(ps[i],qs[i]);
  202. 	}
  203. } querySeg;
  204.  
  205. Pos ps[maxN];
  206. Query qs[maxN];
  207. int be[maxN][2];
  208.  
  209. int main(){
  210. 	memset(be,-1,sizeof(be));
  211. 	int n=read(),p=0,q=0;
  212. 	vector<pii> v;
  213. 	REP(i,n){
  214. 		int t=read();
  215. 		if(t==1){
  216. 			int x=read(),y=read();
  217. 			ps[p]=Pos{x,y};
  218. 			v.PB(MP(p++,0));
  219. 		}else if(t==2){
  220. 			v.PB(MP(read(),1));
  221. 		}else{
  222. 			for(auto x:v)
  223. 				be[x.first][x.second]=q;
  224. 			v.clear();
  225. 			int x=read(),y=read();
  226. 			qs[q]=Query{Pos{x,y},q};
  227. 			q++;
  228. 		}
  229. 	}
  230. 	querySeg.Init(q);
  231. 	REP(i,p){
  232. 		if(be[i][0]==-1)
  233. 			continue;
  234. 		else if(be[i][1]==-1)
  235. 			be[i][1]=querySeg.s;
  236. 		querySeg.AddPos(be[i][0],be[i][1],ps[i]);
  237. 	}
  238. 	REP(i,q)
  239. 		querySeg.AddQuery(i,qs[i]);
  240. 	querySeg.SolveAll();
  241. 	REP(i,q){
  242. 		if(ans[i]==0)ans[i]=-1;
  243. 		printf("%lld\n",ans[i]);
  244. 	}
  245. }
Success #stdin #stdout 0.02s 46944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YIvpMO
language:
C++14 (gcc 8.3)
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!