fork download
copy 
  1. #include <iostream>
  2. #include <string.h>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6. long long int ls[300003];
  7. long long int rs[300003];
  8.  
  9. struct E{
  10. 	int p,no;
  11. 	long long int x;
  12. 	bool operator<(const E& e1)const{
  13. 		if(x!=e1.x)return x<e1.x;
  14. 		return p<e1.p;
  15. 	}
  16. };
  17.  
  18. int main() {
  19. 	memset(ls,-1,sizeof(ls));
  20. 	memset(rs,-1,sizeof(rs));
  21. 	int n;
  22. 	cin>>n;
  23. 	vector<E> vs;
  24. 	for(int i=0;i<n;i++){
  25. 		E e1;
  26. 		cin>>e1.p>>e1.x;
  27. 		e1.no=i;
  28. 		vs.push_back(e1);
  29. 	}
  30. 	sort(vs.begin(),vs.end());
  31. 	int l=0;
  32. 	int r=0;
  33. 	int p=vs[0].p;
  34. 	while(r<n){
  35. 		while(r<n){
  36. 			if(p==vs[r].p){
  37. 				r++;
  38. 			}else{
  39. 				break;
  40. 			}
  41.  
  42. 		}
  43. 		if(n<=r)break;
  44. 		while(l<r){
  45. 			ls[vs[l].no]=vs[r].x-vs[l].x;
  46. 			l++;
  47. 		}
  48. 		p=vs[r].p;
  49. 	}
  50. 	r=n-1;
  51. 	l=n-1;
  52. 	p=vs[l].p;
  53. 	while(0<=l){
  54. 		while(0<=l){
  55. 			if(p==vs[l].p){
  56. 				l--;
  57. 			}else{
  58. 				break;
  59. 			}
  60. 		}
  61. 		if(l<0)break;
  62. 		while(l<r){
  63. 			rs[vs[r].no]=vs[r].x-vs[l].x;
  64. 			r--;
  65. 		}
  66. 		p=vs[l].p;
  67. 	}
  68.  
  69. 	for(int i=0;i<n;i++){
  70. 		//cout<<ls[i]<<" "<<rs[i];
  71. 		if(ls[i]==-1){
  72. 			cout<<rs[i];
  73. 		}else if(rs[i]==-1){
  74. 			cout<<ls[i];
  75. 		}else{
  76. 			cout<<min(ls[i],rs[i]);
  77. 		}
  78. 		cout<<endl;
  79. 	}
  80. 	return 0;
  81. }
Success #stdin #stdout 0.01s 8216KB
comments (?)
stdin
copy 
3
2 5
1 1
1 2
stdout
copy 
3
4
3
https://ideone.com/FKAaeJ
language:
C++ (gcc 8.3)
created:
10 days 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!