BARICAVN - BARICA

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
program BARICAVN;
uses math;
const
  input  = '';
  output = '';
  maxn = 300000;
  maxt = 100000;
type
  rec = record
    x,y,val,pos: integer;
  end;
var
  a: array[1..maxn] of rec;
  maxx,maxy: array[0..maxt] of integer;
  n,k: integer;

procedure init;
var
  f: text;
  i: integer;
begin
  assign(f, input);
    reset(f);

  readln(f, n, k);
  for i := 1 to n do
    begin
      readln(f, a[i].x,a[i].y,a[i].val);
      a[i].pos := i;
    end;

  close(f);
end;

procedure swap(var u,v: rec);
var
  z: rec;
begin
  z := u;  u := v;  v := z;
end;

function lower(u,v: rec): boolean;
begin
  lower := (u.x < v.x) or ((u.x = v.x) and (u.y < v.y));
end;

procedure quicksort;

  procedure par(l,h: integer);
  var
    i,j: integer;
    p: rec;
  begin
    if l >= h then exit;
    i := l; j := h; p := a[random(h - l + 1) + l];

    repeat
      while lower(a[i],p) do inc(i);
      while lower(p,a[j]) do dec(j);

      if i <= j then
        begin
          if i < j then swap(a[i],a[j]);
          inc(i);
          dec(j);
        end;
    until i > j;

    par(l,j);
    par(i,h);
  end;

begin
  par(1,n);
end;

procedure solve;
var
  f: text;
  i,t: integer;
begin
  for i := 0 to maxt do
    begin
      maxx[i] := -maxn;
      maxy[i] := -maxn;
    end;

  i := 1;
  while a[i].pos <> 1 do inc(i);
  maxx[a[i].x] := a[i].val;
  maxy[a[i].y] := a[i].val;

  repeat
    inc(i);
    t := max(maxx[a[i].x],maxy[a[i].y]);
    if t >= k then t := t - k + a[i].val;
    if maxx[a[i].x] < t then maxx[a[i].x] := t;
    if maxy[a[i].y] < t then maxy[a[i].y] := t;
  until a[i].pos = n;

  assign(f, output);
    rewrite(f);
    writeln(f, t);
  close(f);
end;

begin
  init;
  quicksort;
  solve;
end.

Download