Ideone.com

fork download

copy

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100005;
int n;
struct Node{
    int x,y,pos;
    bool operator < (const Node &oth)const{
        if (x<oth.x) return true;
        if (x>oth.x) return false;
        if (y>oth.y) return true;
        return false;
    }
}a[N];
 
int Qt;
int Q[N],Qp[N],Fa[N];
 
void dp(){
    Qt=0;
    int i,l,r,mid,last=1;
    memset(Fa,0xFF,sizeof(Fa));
    memset(Qp,0xFF,sizeof(Qp));
    Q[++Qt]=a[1].y;
    Qp[Qt]=1;
    Qp[0]=-1;
    for (i=2;i<=n;i++){
        if (a[i].y>Q[Qt]){
            Q[++Qt]=a[i].y;
            Qp[Qt]=i;
            Fa[i]=Qp[Qt-1];
            last=i;
        }
        else{
            l=1; r=Qt;
            while (l<r){
                mid=(l+r)/2;
                if ( a[i].y<=Q[mid] ) r=mid;
                                 else l=mid+1;
            }
            Q[l]=a[i].y;
            Qp[l]=i;
            Fa[i]=Qp[l-1];
        }
    }
    printf("%d\n",Qt);
    Qt=0;
    i=last;
    while (i!=-1){
        Q[Qt++]=a[i].pos;
        i=Fa[i];
    }
    sort(Q,Q+Qt);
    for (i=0;i<Qt;i++) printf("%d ",Q[i]);
    puts("");
}
 
int main(){
    int Tc;
    scanf("%d",&Tc);
    while (Tc--){
        scanf("%d",&n);
        for (int i=1;i<=n;i++){
          scanf("%d%d",&a[i].x,&a[i].y);
          a[i].pos=i;
        }
        sort(a+1,a+n+1);
        dp();
        if (Tc) puts("");
    }
}

Runtime error #stdin compilation error #stdout 1.23s 5076KB

stdin

copy

Standard input is empty

compilation info

prog.cpp: In function ‘int main()’:
prog.cpp:64: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:66: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:68: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

stdout

copy

https://ideone.com/boTEV

language:

C++ (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language