fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. // - Đây là một bài vừa đọc vào sẽ thấy đơn giản nhưng ẩn chứa 1 cái bẫy bên trong
  11. // - Với mỗi đoạn thì ngoài thêm l(i), r(i) vào danh sách nén ra thì ta còn phải thêm cả r(i) + 1
  12. // - Một test đơn giản để thấy bẫy: [1, 3], [6, 7], [3, 6]
  13. //   Kết quả đúng là -1 (không có đoạn thoả mãn), nhưng nếu không thêm r(i) + 1 vào danh sách nén thì đoạn [3, 6] lại thoả mãn 
  14. //   Lý do là vì nếu không thêm r(i) + 1 thì khoảng trống giữa đoạn [1, 3] và [6, 7] sẽ không còn!
  15. // - Ngoài cái bẫy trên ra thì phần còn lại của bài rất đơn giản.
  16. const int N = 2e5 + 5; 
  17.  
  18. int n;  
  19. int l[N], r[N]; 
  20. int cnt[3 * N]; 
  21.  
  22. int sz;  
  23. vector<int> vals; 
  24.  
  25. int getVal(int x) {
  26. 	return lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;  
  27. }
  28.  
  29. int main() {
  30. 	ios::sync_with_stdio(0); cin.tie(0);  	
  31. 	cin >> n; 
  32. 	for (int i = 1; i <= n; i++) {
  33. 		cin >> l[i] >> r[i]; 
  34. 		vals.push_back(l[i]); 
  35. 		vals.push_back(r[i]);
  36. 		vals.push_back(r[i] + 1); // important
  37. 	}
  38.  
  39. 	sort(vals.begin(), vals.end());
  40. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());   
  41. 	sz = vals.size();  
  42.  
  43. 	for (int i = 1; i <= n; i++) {
  44. 		cnt[getVal(l[i])]++; 
  45. 		cnt[getVal(r[i] + 1)]--; 
  46. 	}
  47. 	for (int i = 1; i <= sz; i++) cnt[i] += cnt[i - 1]; 
  48. 	// Lúc này cnt[i] chính là số đoạn phủ điểm i 
  49.  
  50. 	for (int i = 1; i <= sz; i++) cnt[i] = (cnt[i] == 1); 
  51. 	for (int i = 1; i <= sz; i++) cnt[i] += cnt[i - 1]; 
  52. 	// Lúc này cnt[i] chính là số điểm từ 1 đến i mà chỉ có 1 đoạn phủ nó
  53.  
  54. 	int ans = -1;  
  55. 	for (int i = 1; i <= n; i++) {
  56. 		if (cnt[getVal(r[i])] - cnt[getVal(l[i]) - 1] == 0) ans = i;  
  57. 	}
  58.  
  59. 	cout << ans << '\n'; 
  60. }
Success #stdin #stdout 0.01s 5600KB
comments (?)
stdin
copy 
3
1 3
4 6
1 7
stdout
copy 
2
https://ideone.com/S9QFLZ
language:
C++14 (gcc 8.3)
created:
158 days ago
visibility:
secret

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!