fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty