Cod sursa(job #1294111)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 16 decembrie 2014 23:30:11
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#define dim 1000003
using namespace std;

ifstream fin("secvmin.in");
ofstream fout("secvmin.out");
int a[dim],b[100003],i,j,n,m,w[100003],k,p,u,mid,nr,x,t[100003];
int drum(int x){
    if(t[x]==0)
        return x;
    return drum(t[x]);
}
int main(){
    fin>>n>>m;
    for(i=1;i<=n;i++)
        fin>>w[i];
    for(i=1;i<=m;i++){
        fin>>k;
        a[k]=i;
    }
    k=0;
    for(i=1;i<=n;i++){
            b[++k]=a[w[i]];
    }
    for(x=1;x<=n && b[x]==0;x++);
    w[1]=x;
    nr=1;
    for(i=2;i<=k;i++)
        if(b[i]!=0){
        if(b[i]>b[w[nr]]){
            w[++nr]=i;
            t[i]=w[nr-1];
        }
        else{
            p=1;u=nr;
            while(p<=u){
                mid=(p+u)/2;
                if(b[i]>b[w[mid]])
                    p=mid+1;
                else
                    u=mid-1;
            }
            if(b[i]>b[w[p-1]]){
                w[p]=i;
                t[i]=w[p-1];
            }
        }
    }
    fout<<w[nr]-drum(w[nr])+1;
    fin.close();fout.close();
    return 0;
}