PERIODNB - PERIOD

Tác giả: ladpro98

Ngôn ngữ: Pascal

program periodnb;
uses    math;
const   fi='';
        maxN=10000007;
type    e=record
        val:int64;
        pos,carry:longint;
        end;
var     a,timer:array[-1..maxN] of int64;
        stack:array[-1..maxN] of e;
        n,head,tail:longint;
        p,q,m,time,res:int64;

procedure input;
var     f:text;
        i:longint;
begin
        assign(f,fi);
        reset(f);
        readln(f,n,time);
        readln(f,p,q,m);
        close(f);
end;

procedure init;
var     i:longint;
        t,pp:int64;
begin
        pp:=0;
        p:=p mod m;
        for i:=1 to n do
        begin
                pp:=pp+p;
                while pp>=m do pp:=pp-m;
                a[i]:=pp + q;
        end;
        for i:=n+1 to n shl 1 do
        a[i]:=a[i-n];
        timer[0]:=0;
        for i:=1 to n shl 1 do
        timer[i]:=timer[i-1]+time;
        for i:=1 to n do
               a[i]:=a[i]+timer[i];
        head:=1;tail:=0;
        res:=high(int64);
end;

procedure process;
var     i:longint;
begin
        for i:=1 to n do
        begin
                while (head<=tail) and (stack[tail].val<=a[i]) do dec(tail);
                inc(tail);
                stack[tail].val:=a[i];
                stack[tail].pos:=i;
                stack[tail].carry:=0;
        end;
        for i:=n+1 to n shl 1 do
        begin
                inc(stack[tail].carry);
                if head<>tail then
                inc(stack[head].carry);
                while (head<=tail) and (stack[head].pos<=(i-n)) do
                begin
                        inc(Head);
                        if head<>tail then
                        inc(stack[head].carry,stack[head-1].carry);
                end;
                a[i]:=a[i]+timer[n];
                while (head<=tail) and ((stack[tail].val-timer[stack[Tail].carry])<=a[i]) do
                begin
                        dec(tail);
                        if head<tail then
                        inc(stack[tail].carry,stack[tail+1].carry);
                end;
                inc(tail);
                stack[tail].val:=a[i];
                stack[tail].pos:=i;
                stack[tail].carry:=0;
                res:=min(res,stack[head].val-timer[stack[Head].carry]);
        end;
end;

begin
        input;
        init;
        process;
        write(res);
end.

Download