单调栈+排序
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 100;
int stk[N], n, a[N], b[N]; // 单调栈:附加求出左边第一个大的值及其序号
pair<pair<int, int>, int>pr[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
int x, y; cin >> x >> y;
pr[i] = {{x, -1 * y}, i};
}
sort(pr + 1, pr + 1 + n);
for (int i = 1; i <= n; i ++) a[i] = -1 * pr[i].first.second;
// 按照左边界从大到小的顺序, 依次寻找该序号左侧第一个比当前序号右边界大的序号
int tt = 0;
for (int i = 1; i <= n; i ++)
{
while (tt && a[stk[tt]] < a[i]) tt --;
if (!tt) b[i] = -1;
else b[i] = stk[tt];
stk[ ++ tt] = i;
}
int flag = 0;
for (int i = n; i > 0; i --)
{
if (b[i] != -1)
{
cout << pr[i].second << " " << pr[b[i]].second << endl;
return 0;
}
}
cout << -1 << " " << -1 << endl;
return 0;
}