Gym 100971D 單調棧

D - Laying Cables Time Limit:2000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u Submit Status Practice Gym 100971D

Description

standard input/output

Announcement

Gym 100971D 單調棧

Statements

One-dimensional country has n cities, the i-th of which is located at the point xi and has population pi, and all xi, as well as all pi, are distinct. When one-dimensional country got the Internet, it was decided to place the main server in the largest city, and to connect any other city j to the city k that has bigger population than j and is the closest to it (if there are many such cities, the largest one should be chosen). City k is called a parent of city j in this case.

Unfortunately, the Ministry of Communications got stuck in determining from where and to where the Internet cables should be laid, and the population of the country is suffering. So you should solve the problem. For every city, find its parent city.

Input

The first line contains a single integer n(1 ≤ n ≤ 200000) — the number of cities.

Each of the next n lines contains two space-separated integers xi and pi(1 ≤ xi, pi ≤ 109) — the coordinate and the population of the i-th city.

Output

Output n space-separated integers. The i-th number should be the parent of the i-th city, or - 1, if the i-th city doesn't have a parent. The cities are numbered from 1 by their order in the input.

Sample Input

Input

Output

-1 4 2 1

Input

Output

-1 1 1

Input

Output

2 -1 2

題意： 給你n個點在x軸上的位置x和權值pos

　　對于一個第i點他的父親定義為和他最近并且權值大于p[i]的為點　　輸出每個點父親，沒有滿足的作其父親的點輸出-1；

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

#define MM(a,b) memset(a,b,sizeof(a));
#define inf 0x7f7f7f7f;
#define FOR(i,n) for(int i=1;i<=n;i++)
#define CT continue;
#define PF printf
const int maxn=200000+10;
struct node{
   int x,id,p,f;
}ne[maxn];
int l[maxn],r[maxn];

bool cmpx(node a,node b)
{
   return a.x<b.x;
}

bool cmpid(node a,node b)
{
   return a.id<b.id;
}

stack<node> stl,str;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        FOR(i,n) scanf("%d%d",&ne[i].x,&ne[i].p),
                 ne[i].id=i;
        while(stl.size()) stl.pop();
        while(str.size()) str.pop();

        sort(ne+1,ne+n+1,cmpx);
        FOR(i,n){
           int id=ne[i].id;
           while(stl.size()&&stl.top().p<=ne[i].p) stl.pop();
           l[id]=stl.empty()?-1:stl.top().id;
           stl.push(ne[i]);
        }

        for(int i=n;i>=1;i--){
           int id=ne[i].id;
           while(str.size()&&str.top().p<=ne[i].p) str.pop();
           r[id]=str.empty()?-1:str.top().id;
           str.push(ne[i]);
        }

        sort(ne+1,ne+n+1,cmpid);
        FOR(i,n){
           if(l[i]==-1&&r[i]==-1) {PF("-1 ");CT;}
           else if(l[i]==-1) {PF("%d ",r[i]);CT;}
           else if(r[i]==-1) {PF("%d ",l[i]);CT;}

           if(ne[r[i]].x-ne[i].x>ne[i].x-ne[l[i]].x) PF("%d ",l[i]);
           else if(ne[r[i]].x-ne[i].x<ne[i].x-ne[l[i]].x) PF("%d ",r[i]);
           else {
               if(ne[r[i]].p>ne[l[i]].p) PF("%d ",r[i]);
               else PF("%d ",l[i]);
           }
        }
        PF("\n");
    }
    return 0;
}

　　錯因分析：剛開始想用lower_bound的，先按x從小到大排好序後，再利用lower_bound查找到枚舉

的點的右側，比目前枚舉點人口數大的第一個點，後來寫了後才想起lower_bound是基于二分查找的，

但是按x排好序後的人口數并不呈現有序性，當然不能用lower_bound；

解決：竟然忘了單調棧這麼典型的算法，左右各掃一遍，記錄大于目前點的最左和最右的點的id，

轉載于:https://www.cnblogs.com/smilesundream/p/5701522.html