[swistoj 327]最小の最大と最大の最小

最小の最大と最大の最小(0327)

Time limit(ms): 2500 Memory limit(kb): 65535 Submission: 329 Accepted: 18
 
問題の説明
また一つのデータ処理問題(><).やはりインputを直接見ましょう.
入力
テストインスタンスのセット.Line 1:2つの数n,m(1<=n<=1000000,1<=m<=100000),nは数値数,mはクエリ回数を表す.Line 2:n個の整数A(i)(0<=A(i)<=10000000)を含む.2つの数の間はスペースで区切られています.次のm行:各行には2つの整数a,b(1<=a<=2,−10000000000<=b<=10000000)が含まれる.クエリーを表します.a=1の場合、n個の数のうちbより小さい数の最大値が出力される.a=2の場合、n個の数のうちbより大きい数の最小値が出力される.条件を満たす数が存在しない場合は-1を出力します.
しゅつりょく
クエリーごとに、答えが出力され、各答えが1行を占めます.
サンプル入力
5 2
1 2 3 3 5
1 3
2 5
サンプル出力
2
-1
 
Hint
SCPC_Zhangjian

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define INF 0x7fffffff

#define N 1000010

 

int n,m;

int a[N];

 

int low_bound(int k)

{

    int l=1,r=n+1;

    while(l<r)

    {

        int m=l+(r-l)/2;

        if(a[m]>=k) r=m;

        else l=m+1;

    }

    return l;

}

int up_bound(int k)

{

    int l=1,r=n+1;

    while(l<r)

    {

        int m=l+(r-l)/2;

        if(a[m]<=k) l=m+1;

        else r=m;

    }

    return l;

}

 

int main()

{

    int i,j,x;

    scanf("%d%d",&n,&m);

    for(i=1;i<=n;i++)

    {

        scanf("%d",&a[i]);

    }

    sort(a+1,a+n+1);  // 、 、 WA、 = =

    while(m--)

    {

        int op,x;

        scanf("%d%d",&op,&x);

        if(op==1 && a[1]>=x || op==2 && a[n]<=x)

        {

            cout<<-1<<endl;

            continue;

        }

        if(op==1)

        {

            int ans=low_bound(x);

            ans--;

            cout<<a[ans]<<endl;

        }

        else

        {

            int ans=up_bound(x);

            cout<<a[ans]<<endl;

        }

    }

    return 0;

}