fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <time.h>
  3. #define min(a,b)    (a<b?(a):(b))
  4. #define max(a,b)    (a>b?(a):(b))
  5. #define lli         long long
  6. #define clr(a,b)    memset(a,b,sizeof(a))
  7. #define getcx 	    getchar_unlocked
  8.  
  9. #define S(a)        scanf("%d",&a);
  10. #define SL(a)       scanf("%lld",&a);
  11. #define SS(a)       scanf("%s",a);
  12. #define PV(v)       { for(int i=0;i<v.size();i++) printf("%d ",v[i]);printf("\n"); }
  13. #define FOR(i,n)    for(int i=0;i<n;i++)
  14. #define REP(i,j,n)  for(int i=j;i<n;i++)
  15.  
  16. void fscani(int *x)
  17. {
  18. 	int n=0;int sign=1;char c=getcx();
  19. 	while(c<'0' || c>'9'){if(c=='-') sign=-1;c=getcx();}
  20. 	while(c>='0' && c<='9'){n=(n<<1)+(n<<3)+(c-'0');c=getcx();}
  21. 	n=n*sign;*x=n;
  22. }
  23. void fscanl(lli *x)
  24. {
  25. 	lli n=0;int sign=1;char c=getcx();
  26. 	while(c<'0' || c>'9'){if(c=='-') sign=-1;	c=getcx();}
  27. 	while(c>='0' && c<='9')	{n=(n<<1)+(n<<3)+(c-'0');c=getcx();}
  28. 	n=n*sign;*x=n;
  29. }
  30.  
  31.  
  32.  
  33.  
  34. //Constants
  35. #define INF     int(2e9)
  36. #define INFL    ((lli)(9e18))
  37. #define MOD     int(1e9 + 7)
  38.  
  39. //General STL
  40. #define tr(cont,it)     for(typeof(cont.begin()) it = cont.begin();it!=cont.end();it++)
  41.  
  42. //Bitwise
  43. #define chkbit(s, b)    (s & ((lli)1<<b))
  44. #define setbit(s, b)    (s |= ((lli)1<<b))
  45. #define clrbit(s, b)    (s &= ~(1<<b))
  46.  
  47. //Vector
  48. #define vi vector<int>
  49. #define vii vector<pair<int,int> >
  50. #define pb push_back
  51.  
  52. //Pair
  53. #define ii pair<int,int>
  54. #define lili pair<long long,long long>
  55. #define mp make_pair
  56.  
  57. //Error Check
  58. #define chk(a)      	cout << #a << " : " << a << endl
  59. #define chk2(a,b)   	cout << endl << #a << " : " << a << "\t" << #b << " : " << b << endl
  60. #define chk3(a,b,c)     cout << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << endl
  61. #define chk4(a,b,c,d)   cout << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << "\t" << #d << " : " << d << endl
  62. #define gc      	getchar();
  63.  
  64. using namespace std;
  65. int dp[6010][6010];
  66. vi mapx,mapy;
  67.  
  68. int find(int x,int y)
  69. {
  70. 	int fx = lower_bound(mapx.begin(),mapx.end(),x) - mapx.begin();
  71. 	int fy = lower_bound(mapy.begin(),mapy.end(),y) - mapy.begin();
  72. 	// cout << fx << " , " << fy << " = " << dp[fx][fy]  << endl;
  73. 	return dp[fx][fy];
  74. }
  75.  
  76. int main(int argc,char *argv[])
  77. {
  78. 	int t=1;
  79. 	REP(z,1,t+1)
  80. 	{
  81. 		int n; cin >> n; //Number of points
  82. 		vector<ii > v;
  83. 		set<ii> s;
  84. 		FOR(i,n) { int x,y; cin >> x >> y ; v.pb(ii(x,y));s.insert(ii(x,y)); }
  85. 		assert ( v.size() == s.size());
  86. 		set<int> vx,vy;
  87. 		FOR(i,n) { vx.insert(v[i].first); vy.insert(v[i].second); }
  88. 		int pre = -1;
  89. 		fprintf(stderr,"----Input Done\n");
  90. 		tr(vx,it)
  91. 		{
  92. 			if(pre < *it-1)
  93. 				mapx.pb(*it-1);
  94. 			mapx.pb(*it);
  95. 			pre = *it;
  96. 		}
  97. 		mapx.pb(2147483642);
  98. 		pre = -1;
  99. 		tr(vy,it)
  100. 		{
  101. 			if(pre < *it - 1)
  102. 				mapy.pb(*it-1);
  103. 			mapy.pb(*it);
  104. 			pre = *it;
  105. 		}
  106. 		mapy.pb(2147483642);
  107. 		FOR(i,mapx.size())
  108. 		{
  109. 			dp[i][0] = 0;
  110. 		}		
  111. 		FOR(i,mapy.size())
  112. 		{
  113. 			dp[0][i] = 0;
  114. 		}
  115. 		FOR(i,v.size())
  116. 		{
  117. 			dp[lower_bound(mapx.begin(),mapx.end(),v[i].first) - mapx.begin()][lower_bound(mapy.begin(),mapy.end(),v[i].second) - mapy.begin()] = 1;
  118. 		}
  119. 		REP(i,1,mapx.size())
  120. 			REP(j,1,mapy.size())
  121. 			{
  122. 				dp[i][j] = dp[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
  123. 			}
  124. 		fprintf(stderr,"----Preprocessing Done\n");
  125. 		int q;
  126. 		cin >> q;
  127. 		// chk(q);
  128. 		FOR(i,q)
  129. 		{
  130. 			int x,y,k;
  131. 			cin >> x >> y >> k;
  132. 			if (k > n)
  133. 			{
  134. 				cout << -1 << endl;
  135. 				continue;
  136. 			}
  137. 			int ans = 0;
  138. 			lli beg = 0, end = 1000000100;
  139. 		       	while(beg <= end)
  140. 			{
  141. 				 // chk2(beg,end);
  142. 				lli mid = (beg + end) / 2;
  143. 				int curAns = find(x+mid,y+mid) - find(x-mid-1,y+mid) - find(x+mid,y-mid-1) + find(x-mid-1,y-mid-1);
  144. 				// chk2(mid,curAns);
  145. 				// mid--;
  146. 				// int preAns = find(x+mid,y+mid) - find(x-mid-1,y+mid) - find(x+mid,y-mid-1) + find(x-mid-1,y-mid-1);
  147. 				// mid++;
  148. 				if(curAns >= k) 
  149. 				{
  150. 					ans = mid;
  151. 					end = mid-1;
  152. 				}
  153. 				else 
  154. 					beg = mid+1;
  155. 			}
  156. 			cout << ans << endl;
  157. 			// if(i%10000==0)
  158. 			// fprintf(stderr,"----Query %d Processed\n",i);
  159. 		}
  160. 	}
  161. 	return 0;
  162.  }
  163.  
Success #stdin #stdout #stderr 0s 144576KB
comments ()
stdin
copy 
3
1 1
2 2
3 1
4
2 3 1
2 2 1
3 2 1
3 3 4
stdout
copy 
1
0
1
-1
stderr
copy 
----Input Done
----Preprocessing Done
https://ideone.com/513Ybz
language:
C++ (gcc 8.3)
created:
9 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!