1025.cpp

ZJU ACM 1010排名第一的程序. 1025的高效程序

#include <stdio.h>

const int N = 5000, L = 1023;

int a[N+1], n;

struct get {
  int l;
  bool b[128];
  char buf[L+1];
  get() {
    for (int i='0'; i<='9'; i++) b[i]=1;
    l=fread(buf,1,L,stdin); buf[l]=0; l=0;
  }
  int operator()() {
    int r=0, ch;
    while(b[ch=buf[l++]])r=10*r+(ch&0xF);
    if (ch==0) {
      l=fread(buf,1,L,stdin); buf[l]=0; l=0;
      while(b[ch=buf[l++]])r=10*r+(ch&0xF);
    }
    return r;
  }
} geti;

int nlis() {
  int l, h, m, k, t=0;
  a[0]&=0xFFFF;
  for (int i=1; i<n; i++) {
    l=0; h=t; k=a[i]&0xFFFF;
    while (l<=h) k<=a[m=l+h>>1]?(h=m-1):(l=m+1);
    a[l]=k; t>?=l;
  }
  return t+1;
}

void sort(int left, int right) {
  if (left<right) {
    int l=left, h=right, v=a[l];
    while (l<h) {
      while(l<h&&v>=a[h])h--; if(l<h)a[l++]=a[h];
      while(l<h&&a[l]>=v)l++; if(l<h)a[h--]=a[l];
    }
    a[h]=v; sort(left,h-1); sort(h+1,right);
  }
}

int main() {
  int t=geti();
  while (t--) {
    n=geti();
    for (int i=0; i<n; i++) a[i]=geti()<<16|geti();
    sort(0,n-1);
    printf("%d\n",nlis());
  }
  return 0;
}