题目链接：http://codeforces.com/gym/101149/problem/G
题目大意：给你n对数字，为(a[i], b[i])，给你m对数字，为(w[i], c[i])。给n对数字找配对，这个配对必须是m中的，而且m中的每个只能和n中的配对一次。
配对条件，w[i]>=a[j], c[i]>=b[j]即可配对。
输出n个数字，每个数字在m个数字当中的配对。
思路：假定n对数字的是x，m对数字的是y
离散化以后sort一下x和y，这样我们就得到了第一维是排序好了的。
然后我们暴力x，每次都把a[i]的值相同的放入线段树，线段树里面储存的是b[i]。
然后如果a[i] != a[i+1]，那么我们就暴力y，对于y，暴力其中所有的w[j] < a[i+1]的，然后再线段树中找离c[i]左边最近的那个数字即可。
ORZ，第一次知道queue这么消耗空间，一直MLE了。
//看看会不会爆int!数组会不会少了一维！
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int inf = 0x3f3f3f3f;
const int maxn = 4e5 + ;
const int maxf = 2e5 + ;
int n, m;
pair<int, pair<int, int> > a[maxf];
pair<int, pair<int, int> > b[maxf];
vector<int> ve;
vector<int> que[maxn * ];
/*
线段树上二分，每次找到和当前的pos最靠近的左端的即可。并且每次保存id
*/
struct Tree{
int cost;
int lft;
}tree[maxn << ];
int ans[maxf]; int update(int pos, int l, int r, int o, int add, int ID = ){
if (pos == l && pos == r){
tree[o].cost += add;
if (add == ) {que[l].push_back(ID); return ;}
if (add == -) {
ID = que[l][tree[o].lft]; tree[o].lft++; return ID;
}
}
int mid = (l + r) / ;
int id = ;
if (pos <= mid) id = update(pos, l, mid, o << , add, ID);
if (pos > mid) id = update(pos, mid + , r, o << | , add, ID);
tree[o].cost = tree[o << ].cost + tree[o << | ].cost;
return id;
} int query(int ql, int qr, int l, int r, int o){
if (l == r){
return l;
}
int mid = (l + r) / ;
int res = ;
if (qr > mid && tree[o << | ].cost > )
res = max(res, query(ql, qr, mid + , r, o << | ));
if (res == && ql <= mid && tree[o << ].cost > )
res = max(res, query(ql, qr, l, mid, o << ));
return res;
} void solve(){
int len = ve.size();
int pos2 = ;
while (b[pos2].fi < a[].fi) pos2++;
a[n + ] = mk(inf, mk(inf, inf));
for(int i = ; i <= n; i++){
update(a[i].se.fi, , len, , , a[i].se.se);
if(a[i].fi != a[i + ].fi) {
while (pos2 <= m && b[pos2].fi < a[i + ].fi){
if (tree[].cost != ){
int x = query(, b[pos2].se.fi, , len, );
if (x){
int id = update(x, , len, , -);
ans[id] = b[pos2].se.se;
}
}
pos2++;
}
}
}
for (int i = ; i <= n; i++){
if (ans[i] == ) {
printf("-1\n"); return;
}
}
for (int i = ; i <= n; i++){
printf("%d%c", ans[i], i == n ? '\n' : ' ');
}
} int main(){
scanf("%d", &n);
for (int i = ; i <= n; i++){
scanf("%d%d", &a[i].fi, &a[i].se.fi);
a[i].se.se = i;
ve.push_back(a[i].fi);
ve.push_back(a[i].se.fi);
}
scanf("%d", &m);
for (int i = ; i <= m; i++){
scanf("%d%d", &b[i].fi, &b[i].se.fi);
b[i].se.se = i;
ve.push_back(b[i].fi);
ve.push_back(b[i].se.fi);
}
if (n > m) {
printf("-1\n"); return ;
}
sort(ALL(ve));
ve.erase(unique(ve.begin(), ve.end()), ve.end());
for (int i = ; i <= n; i++){
a[i].fi = lower_bound(ALL(ve), a[i].fi) - ve.begin() + ;
a[i].se.fi = lower_bound(ALL(ve), a[i].se.fi) - ve.begin() + ;
}
for (int i = ; i <= m; i++){
b[i].fi = lower_bound(ALL(ve), b[i].fi) - ve.begin() + ;
b[i].se.fi = lower_bound(ALL(ve), b[i].se.fi) - ve.begin() + ;
}
sort(a + , a + + n);
sort(b + , b + + m);
solve();
return ;
}