FIRS - Hàng cây

Tác giả: ladpro98

Ngôn ngữ: Pascal

program firs;
uses    math;
const   fi='';
        maxN=123456;
type    e=record
        v,pos:longint;
        end;
var     a:array[1..maxN] of e;
        p:array[1..maxN] of longint;
        check:array[1..maxN] of boolean;
        n,res:longint;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        begin
                read(inp,a[i].v);
                a[i].pos:=i;
        end;
        close(inp);
end;

procedure swap(i,j:longint);
var     t:e;
begin
        t:=a[i];
        a[i]:=a[j];
        a[j]:=t;
end;

procedure sort(l,r:longint);
var     i,j:longint;
        p:e;
begin
        if l>=r then exit;
        p:=a[random(r-l+1)+l];
        i:=l;j:=r;
        repeat
                while (a[i].v<p.v) or ((a[i].v=p.v) and (a[i].pos<p.pos)) do inc(i);
                while (a[j].v>p.v) or ((a[j].v=p.v) and (a[j].pos>p.pos)) do dec(j);
                if i<=j then
                begin
                        if i<j then swap(i,j);
                        inc(i);
                        dec(j);
                end;
        until i>j;
        sort(l,j);sort(i,r);
end;

procedure init;
var     i:longint;
begin
        for i:=1 to n do
        p[a[i].pos]:=i;
end;

procedure process;
var     i:longint;
begin
        for i:=1 to n do
        if not check[i] then
        begin
                inc(res);
                check[i]:=true;
                if a[i].pos>1 then
                check[p[a[i].pos-1]]:=true;
                if a[i].pos<n then
                check[p[a[i].pos+1]]:=true;
        end;
end;

begin
        input;
        sort(1,n);
        init;
        process;
        write(res);
end.

Download