fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	ios::sync_with_stdio(0), cin.tie(0);
  6. 	int N, Q; cin >> N >> Q;
  7. 	vector<int> H(N); for (int& h : H) cin >> h;
  8.  
  9. 	vector<vector<pair<int, int>>> queries(N);
  10. 	for (int q = 0; q < Q; q++) {
  11. 		int a, b; cin >> a >> b; a--;
  12. 		queries[a].emplace_back(b, q);
  13. 	}
  14. 	vector<int> ans(Q);
  15.  
  16. 	vector<int> forwardLis(N);
  17. 	int LIS;
  18. 	{
  19. 		vector<int> buf; buf.reserve(N);
  20. 		for (int i = 0; i < N; i++) {
  21. 			for (auto q : queries[i]) {
  22. 				ans[q.second] = int(lower_bound(buf.begin(), buf.end(), q.first) - buf.begin());
  23. 			}
  24. 			auto it = lower_bound(buf.begin(), buf.end(), H[i]);
  25. 			forwardLis[i] = int(it - buf.begin());
  26. 			if (it == buf.end()) buf.push_back(H[i]);
  27. 			else *it = H[i];
  28. 		}
  29. 		LIS = int(buf.size());
  30. 	}
  31.  
  32. 	vector<int> numCnd(LIS);
  33. 	{
  34. 		vector<int> buf; buf.reserve(N);
  35. 		for (int i = N-1; i >= 0; i--) {
  36. 			for (auto q : queries[i]) {
  37. 				ans[q.second] += int(lower_bound(buf.begin(), buf.end(), q.first, std::greater<int>()) - buf.begin());
  38. 			}
  39. 			auto it = lower_bound(buf.begin(), buf.end(), H[i], std::greater<int>());
  40. 			int backwardLis = int(it - buf.begin());
  41. 			if (it == buf.end()) buf.push_back(H[i]);
  42. 			else *it = H[i];
  43.  
  44. 			if (forwardLis[i] + backwardLis + 1 == LIS) {
  45. 				numCnd[forwardLis[i]]++;
  46. 			} else {
  47. 				forwardLis[i] = -1;
  48. 			}
  49. 		}
  50. 	}
  51.  
  52. 	for (int i = 0; i < N; i++) {
  53. 		int base = LIS - (forwardLis[i] != -1 && numCnd[forwardLis[i]] == 1);
  54. 		for (auto q : queries[i]) {
  55. 			ans[q.second] = max(ans[q.second]+1, base);
  56. 		}
  57. 	}
  58.  
  59. 	for (int v : ans) { cout << v << '\n'; }
  60.  
  61. 	return 0;
  62. }
Success #stdin #stdout 0s 4348KB
comments (?)
stdin 
4 4
1 2 3 4
1 1
1 4
4 3
4 5
stdout 
4
3
3
4
https://ideone.com/iHuO3i
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!