MINROAD - VOI 2014 - Con đường Tùng Trúc

Tác giả: ladpro98

Ngôn ngữ: Pascal

program minroad;
uses    math;

type    e=record
        x,t:longint;
        end;

const   fi      = '';
        fo      = '';
        maxN    = 300050;

var     a               :array[1..maxN] of e;
        truc,tung       :array[0..maxN] of longint;
        n,res,p,q       :longint;

procedure input;
var     f:text;
        i:longint;
begin
        assign(f,fi);
        reset(f);
        readln(f,n,p,q);
        for i:=1 to n do
        readln(f,a[i].x,a[i].t);
        close(f);
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     p,i,j:longint;
begin
        if l>=r then exit;
        p:=a[random(r-l+1)+l].x;
        i:=l;j:=r;
        repeat
                while a[i].x<p do inc(i);
                while a[j].x>p 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
        if a[i].t=1 then
        begin
                tung[i]:=tung[i-1]+1;
                truc[i]:=truc[i-1];
        end
        else
        begin
                tung[i]:=tung[i-1];
                truc[i]:=truc[i-1]+1;
        end;
end;

procedure process;
var     i,j:longint;
begin
        res:=high(longint);
        j:=2;
        for i:=1 to n do
        begin
                while (j<=n) and (((tung[j]-tung[i-1])<p) or ((truc[j]-truc[i-1])<q)) do
                        inc(j);
                if j<=n then
                res:=min(res,a[j].x-a[i].x);
        end;
end;

procedure output;
var     f:text;
begin
        assign(f,fo);
        rewrite(f);
        if res=high(longint) then res:=-1;
        write(f,res);
        close(f);
end;

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

Download