fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 200005;
  4. struct zorc {
  5. 	int a, b, index;
  6. 	bool operator < (const zorc z) const {
  7. 		return (a > z.a) || (a == z.a && b > z.b);
  8. 	}
  9. }Zorcs[N];
  10. struct axe {
  11. 	int w, c, index;
  12. 	bool operator <(const axe a) const {
  13. 		return (w < a.w) || (w == a.w && c < a.c) || (w == a.w && c == a.c && index < a.index);
  14. 	}
  15. }Axe[N];
  16. int n, m;
  17. int bs(int key) {
  18. 	int s = 0, e = m - 1, ans = -1;
  19. 	while(s <= e) {
  20. 		int mid = (s + e) / 2;
  21. 		if (Axe[mid].w >= key) {
  22. 			ans = mid;
  23. 			e = mid - 1;
  24. 		} else
  25. 			s = mid + 1;
  26. 	}
  27. 	return ans;
  28. }
  29. int ans[N];
  30. int main() {
  31. 	scanf("%d", &n);
  32. 	for (int i = 0; i < n; i++) {
  33. 		zorc z;
  34. 		scanf("%d %d", &z.a, &z.b);
  35. 		z.index = i + 1;
  36. 		Zorcs[i] = z;
  37. 	}
  38. 	scanf("%d", &m);
  39. 	for (int i = 0; i < m; i++) {
  40. 		axe a;
  41. 		scanf("%d %d", &a.w, &a.c);
  42. 		a.index = i + 1;
  43. 		Axe[i] = a;
  44. 	}
  45. 	if (m < n){
  46. 		puts("-1");
  47. 		return 0;
  48. 	}
  49. 	sort(Zorcs, Zorcs + n);
  50. 	sort(Axe, Axe + m);
  51.  
  52. 	set <axe> st;
  53. 	int soFar = m;
  54.  
  55. 	for (int i = 0; i < n; i++) {
  56. 		int idx = bs(Zorcs[i].a);
  57. 		if (idx == -1) {
  58. 			puts("-1");
  59. 			return 0;
  60. 		}
  61.  
  62. 		for (int j = idx; j < soFar; j++) {
  63. 			axe a = {Axe[j].c, Axe[j].w, Axe[j].index};
  64. 			st.insert(a);
  65. 		}
  66. 		soFar = idx;
  67. 		auto A = st.lower_bound({Zorcs[i].b, 0, 0});
  68. 		if (A == st.end()){
  69. 			puts("-1");
  70. 			return 0;
  71. 		}
  72.  
  73. 		st.erase(A);
  74. 		ans[Zorcs[i].index] = A->index;
  75. 	}
  76. 	for (int i = 1; i <= n; i++)
  77. 		printf("%d ", ans[i]);
  78.  
  79. 	return 0;
  80. }
Success #stdin #stdout 0s 8944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZCajSm
language:
C++14 (gcc 8.3)
created:
8 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!