fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using i64 = int64_t;
  5.  
  6. struct frac {
  7. 	int n, d;
  8. 	frac(int n_, int d_) : n(n_), d(d_) {
  9. 		int g = __gcd(n, d);
  10. 		n /= g, d /= g;
  11. 		if (d < 0) {
  12. 			n = -n, d = -d;
  13. 		}
  14. 	}
  15. 	frac(int n_) : frac(n_, 1) {}
  16. 	frac() : frac(0) {}
  17.  
  18. 	friend std::ostream& operator << (std::ostream& o, const frac& f) {
  19. 		return o << f.n << '/' << f.d;
  20. 	}
  21.  
  22. 	friend bool operator < (const frac& a, const frac& b) { return i64(a.n) * b.d < i64(a.d) * b.n; }
  23. 	friend bool operator == (const frac& a, const frac& b) { return a.n == b.n && a.d == b.d; }
  24. 	friend bool operator != (const frac& a, const frac& b) { return !(a == b); }
  25. };
  26.  
  27. using line_t = pair<int, int>;
  28.  
  29. const int INF = 1e9;
  30.  
  31. const int MAXN = 2.1e5;
  32. int N;
  33. line_t L[MAXN];
  34.  
  35. int Q[MAXN];
  36.  
  37. frac ans[MAXN];
  38.  
  39. frac lastBetter(const line_t& a, const line_t& b) {
  40. 	assert(a.second < b.second);
  41. 	assert(a.first != b.first);
  42. 	if (a.first < b.first) {
  43. 		return INF;
  44. 	} else {
  45. 		return frac(b.second - a.second, a.first - b.first);
  46. 	}
  47. }
  48.  
  49. deque<pair<line_t, frac>> dq;
  50.  
  51. void add(const line_t& l) {
  52. 	while (!dq.empty()) {
  53. 		frac f = lastBetter(l, dq.front().first);
  54. 		if (!(f < dq.front().second)) {
  55. 			dq.pop_front();
  56. 		} else {
  57. 			break;
  58. 		}
  59. 	}
  60. 	if (dq.empty()) {
  61. 		dq.emplace_front(l, INF);
  62. 	} else {
  63. 		dq.emplace_front(l, lastBetter(l, dq.front().first));
  64. 	}
  65. }
  66.  
  67. frac query(const line_t& l) {
  68. 	if (l.first <= dq.back().first.first) return -1;
  69. 	int mi = -1, ma = int(dq.size())-1;
  70. 	while (ma - mi > 1) {
  71. 		int md = (mi + ma) / 2;
  72. 		if (!(dq[md].second < lastBetter(l, dq[md].first))) {
  73. 			ma = md;
  74. 		} else {
  75. 			mi = md;
  76. 		}
  77. 	}
  78. 	return lastBetter(l, dq[ma].first);
  79. }
  80.  
  81. void go() {
  82. 	vector<int> lines(N); iota(lines.begin(), lines.end(), 0);
  83. 	sort(lines.begin(), lines.end(), [&](int i, int j) { return L[i].second > L[j].second; });
  84. 	dq = {};
  85. 	for (int i : lines) {
  86. 		add(L[i]);
  87. 		if (L[i].second > L[Q[i]].second) {
  88. 			ans[i] = query(L[Q[i]]);
  89. 		}
  90. 	}
  91. }
  92.  
  93. int main() {
  94. 	ios::sync_with_stdio(0), cin.tie(0);
  95.  
  96. 	cin >> N;
  97. 	for (int i = 0; i < N; i++) {
  98. 		L[i].first = -(i+1);
  99. 		cin >> L[i].second;
  100. 	}
  101. 	for (int i = 0; i < N; i++) {
  102. 		cin >> Q[i]; Q[i]--;
  103. 		assert(i != Q[i]);
  104. 	}
  105.  
  106. 	go();
  107. 	for (int i = 0; i < N; i++) {
  108. 		L[i].first *= -1;
  109. 		L[i].second *= -1;
  110. 	}
  111. 	go();
  112.  
  113. 	for (int i = 0; i < N; i++) {
  114. 		if (ans[i] == -1) {
  115. 			cout << -1 << '\n';
  116. 		} else {
  117. 			cout << ans[i] << '\n';
  118. 		}
  119. 	}
  120.  
  121. 	return 0;
  122. }
  123.  
Success #stdin #stdout 0s 5160KB
comments (?)
stdin
copy 
4
3 5 10 2
3 3 2 1
stdout
copy 
7/2
7/2
5/1
-1
https://ideone.com/dcygWL
language:
C++14 (gcc 8.3)
created:
4 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!