Tom Sawyer has many friends who paints his fence. Each friend painted contiguous part of the fence. Some planks could stay unpainted, some could be painted several times. Program must output the number of painted planks.
Input format:
First line: N smaller than 100000 - number of Tom Sawyer's friends.
N lines (for each friend):
a
,b
smaller than 109 - numbers (from the beginning of the fence) of the first painted by the person plank and the last painted by the person plank.Example:
Input:
3 1 2 4 5 2 4
Output:
5
The problem is: program must work no more than 1 second on every test.
I've written many programs of different work ideas, but all of them are not fast enough. I work with online automatic system that checks my code on inputs that are unknown for me, and the system says on some tests that running the program takes 1.032, 1.036 seconds - more than a second.
Example of a working program (idea is to make all segments non-intersecting):
program sortirovkaI;
var a,b:array[1..100000] of longint;
{a - array of numbers of first planks for each person}
{b - array of numbers of last planks for each person}
n,m,i,j:longint;
procedure peresech(var a1,b1,a2,b2:longint);
{processing two segments [a1,b1], [a2,b2] - making them non-intersecting}
{if two segments intersect, procedure will make one of them bigger}
{ and "kill" another - make it [-1,-1]}
begin
if (a1>b2) or (a2>b1) or (a1=-1) or (a2=-1) then
exit;
if a2<a1 then a1:=a2;
if b2>b1 then b1:=b2;
a2:=-1;
b2:=-1;
end;
begin
readln(n);
for i:=1 to n do
read(a[i],b[i]); {filling the arrays}
for i:=2 to n do {for each segment, except the first}
for j:=1 to i-1 do
peresech(a[i],b[i],a[j],b[j]); {make it non-intersecting with every}
{preceding segment}
m:=0; {summarize the lengths of all "not killed" segments}
for i:=1 to n do
if a[i]<>-1 then m:=m+b[i]-a[i]+1;
writeln(m); {output}
end.
One more example of working program (idea is to "go" along the fence from the beginning to the end):
program sortirovkaI;
var a,b:array[1..100000] of longint;
{a - array of numbers of first planks for each person}
{b - array of numbers of last planks for each person}
n,m,i,j,v,t:longint;
begin
readln(n);
for i:=1 to n do
read(a[i],b[i]); {filling the arrays}
{sorting the segments - a[1]<a[2]<a[3]<...<a[n]}
{ b[1] b[2] b[3] ... b[n]}
{method of inserts - the fastest known on my level}
for v:=1 to n-1 do
begin
i:=v;
while (i>0) and (a[v+1]<a[i]) do i:=i-1;
if i<v then
begin
t:=a[v+1];
for j:=v+1 downto i+2 do a[j]:=a[j-1];
a[i+1]:=t;
t:=b[v+1];
for j:=v+1 downto i+2 do b[j]:=b[j-1];
b[i+1]:=t;
end;
end;
{now start going along the fence}
t:=b[1]; {t is the number of current plank}
m:=b[1]-a[1]+1; {m is the number of painted planks that we've already seen}
for i:=2 to n do {consider every segment}
begin
if a[i]>t then {we see ahead some non-painted planks}
{ and then current segment}
begin
m:=m+b[i]-a[i]+1; {add length of segment to m}
t:=b[i]; {go to the end of the segment}
end
else {the beginning of the segment is somewhere behind us}
if b[i]>t then {but we can see ahead the ending of the segment}
begin
m:=m+b[i]-t; {add to m the way from "here" to the end of current segment}
t:=b[i]; {go to the end of the segment}
end;
end;
{we need sorting because while going along the fence we can go only forward}
writeln(m); {output}
end.
One more example of code - the last idea, but without sorting the arrays:
program sortirovkaI;
var a,b:array[1..100000] of longint;
n,m,i,j,t,bmax,r:longint;
f:boolean;
begin
readln(n);
for i:=1 to n do {input}
read(a[i],b[i]);
bmax:=b[1];
for i:=1 to n do {searching for the max element n array B }
if b[i]>bmax then bmax:=b[i]; { - the end of the fence}
j:=1;
for i:=1 to n do
if a[i]<a[j] then j:=i; {searching for the index of min element in array A}
t:=a[j];
a[j]:=a[1]; {making the first segment start with min value}
a[1]:=t; {changing a[1],b[1] and a[j],b[j]}
t:=b[j];
b[j]:=b[1];
b[1]:=t;
{now start going along the fence}
t:=b[1]; {t is the number of current plank}
m:=b[1]-a[1]+1; {m is the number of painted planks that we have already seen}
a[1]:=-1; b[1]:=-1; {kill the segment}
repeat
f:=false;
for i:=2 to n do
begin
if t=bmax then {if it is end of the fence}
begin
writeln(m);
exit;
end;
if a[i]=-1 then continue; {if the segment is killed}
if a[i]<=t+1 then {if ahead us are painted planks of current segmant}
begin
if b[i]>t then
begin
m:=m+b[i]-t; {add to m number of planks from here to the end of current segment}
t:=b[i]; {go to the end of the segment}
end;
a[i]:=-1; b[i]:=-1; {kill the segment}
f:=true;
end;
end;
if not f then {if there are non-painted planks ahead}
begin
i:=1;
while a[i]<t do i:=i+1; {searching for the index of min element in array A}
j:=i; {it is number of the first painted plank we can see}
for i:=i to n do
if (a[i]<a[j]) and (a[i]>t) then j:=i;
r:=a[j];
a[j]:=a[1];
a[1]:=r; {making the first segment start with min value}
r:=b[j];
b[j]:=b[1];
b[1]:=r;
t:=b[1]; {t is the number of current plank}
m:=m+b[1]-a[1]+1; {m is the number of painted planks that we have already seen}
a[1]:=-1; b[1]:=-1; {kill the segment}
end;
until t=bmax; {until we reach the end of the fence}
writeln(m); {output}
end.
This last one is the fastest, but still takes more than a second on some tests.