http://acm.pku.edu.cn/JudgeOnline/problem?id=1201
Код:
program PKU1201;
{$i-,s-,q-,r-}
const maxn = 100000;
type integer = longint;
var a, b, c, s: array[1..maxn] of integer;
h: array[1..maxn] of boolean;
n, m: integer;
var tmp1: integer;
procedure swap(var i, j: integer);
begin
tmp1 := i; i := j; j := tmp1;
end;
procedure sort(l, r: integer);
var i, j, mid: integer;
begin
i := l; j := r; mid := b[(l + r) shr 1];
while i <= j do begin
while b[i] < mid do i := i + 1;
while b[j] > mid do j := j - 1;
if i <= j then begin
swap(a[i], a[j]); swap(b[i], b[j]); swap(c[i], c[j]);
i := i + 1; j := j - 1;
end;
end;
if i < r then sort(i, r);
if l < j then sort(l, j);
end;
procedure prepare;
var i: integer;
begin
read(n);
for i := 1 to n do begin
read(a[i], b[i], c[i]);
inc(a[i]); inc(b[i]);
end;
sort(1, n);
end;
var sum: integer;
function calc(k: integer): integer;
begin
sum := 0;
while k > 0 do begin
sum := sum + s[k];
k := k - k and (k xor (k - 1));
end;
calc := sum;
end;
procedure add(k: integer);
begin
while k <= m do begin
s[k] := s[k] + 1;
k := k + k and (k xor (k - 1));
end;
end;
procedure main;
var i, j, now: integer;
begin
fillchar(s, sizeof(s), 0);
fillchar(h, sizeof(h), true);
m := b[n];
for i := 1 to n do begin
now := calc(b[i]) - calc(a[i] - 1);
now := c[i] - now;
if now > 0 then
for j := b[i] downto a[i] do if h[j] then begin
add(j); h[j] := false;
now := now - 1;
if now = 0 then break;
end;
end;
writeln(calc(m));
end;
begin
prepare;
main;
end.