u can search for intersections instead of looking for cutouts, just invert the segments of the second function
use min max instead of a lot of conditions and you get a very simple code :)

I just don't know what is wrong.I need some test in order to pass test 8

3
1 2 10
2 3 100
3 4 1000
1
1 2 10

Answer: 2 2 3 100 3 4 1000

In test 10 this sample helped me

1 1 10 2
2 1 3 2 7 10 2

Ans is :
1 3 7 2

The test below helped me on WA#9.

2 0 5 12 5 10 13
1 3 7 21
Right answer: 2 0 3 12 7 10 13.

1)Рассмотреть по-честному ВСЕ случаи( их не более 8);
2)Лучше использовать массив размером 50001 элемент(у меня с 15001 не прошло);
3)Лучше использовать тип данных longint( >50000),т.к. с integer не прошло.

Is it possible to solve this problem with Python 3 or Scala? I got TLE with same linear algo on both langauges (tried mutable and immutable collections in Scala and so I think there are problems with slow input) but got AC (in 0.171 sec) only with pure Java solution.

Edited by author 21.10.2014 13:07

I can't understand why my program work slow, I don't know any algorithm that can solvе this problem in beter time. My program solve it in 0.125s, when others in 0.031. Why ? Please help me :)

New tests were added, and time limit was decreased to 0.5 sec. 183 authors lost AC after rejudge.

I think that second test contains line which begins with 0. This case is not allowed because in problem statement is written that (1 ≤ N ≤ 14999). Please check if I'm right.

In one of my solution I checked (using assert from cassert) if N is greater than 0 and I received WA2. When I removed assert I've received AC.

increase size of array.
15000 (not 14999)
Edited by author 25.07.2010 03:39

Edited by author 25.07.2010 03:40

Try this:
2 1 2 2 2 3 3
0

Right answer:
2 1 2 2 2 3 3

I had WA, and now I have AC!

Edited by author 01.10.2007 20:17

Edited by author 01.10.2007 20:17

This test helped me pass test #10! I hope it will help you too.
2 1 2 3 2 3 4
0
---
And answer 2 1 2 3 2 3 4.

And just good test
5 1 5 2 6 7 3 8 9 3 11 15 3 17 20 4
4 6 8 4 9 10 4 12 14 2 17 19 2
---
And answer 5 1 5 2 8 9 3 11 12 3 14 15 3 19 20 4
GOOD LUCK!

I think it's simple to model this process, but I got WA10. Could you help me? Give me some tests, please.
I tried all tests from forum and my program gives right answers at all of them.

Edited by author 21.02.2006 21:46

Crash (access violation)

My code:

Program t1116;

Const MaxN=15000;

Type Kusok=record A,B,Y :integer end;

Var F1,F2,F      :array[1..MaxN]of Kusok;
    n1,n2,i,j,n  :integer;
    j1,j2,i2     :integer;

begin
read(n1);for i:=1 to n1 do read(f1[i].a,f1[i].b,f1[i].y);
read(n2);for i:=1 to n2 do read(f2[i].a,f2[i].b,f2[i].y);
n:=0;
j1:=1;
j2:=1;
for j1:=1 to n1 do begin
 for i2:=j2 to n2 do begin
  if f1[j1].b<f2[i2].a then break;
  if (f1[j1].a<f2[i2].a)and(f1[j1].b>f2[i2].b) then begin
    n:=n+1;
    f[n].a:=f1[j1].a;
    f[n].b:=f2[i2].a;
    f[n].y:=f1[j1].y;
    f1[j1].b:=f2[i2].b;
   end else
  if (f1[j1].a<f2[i2].a)and(f1[j1].b<f2[i2].b) then begin
    n:=n+1;
    f[n].a:=f1[j1].a;
    f[n].b:=f2[i2].a;
    f[n].y:=f1[j1].y;
    f1[j1].a:=f1[j1].b;
    break;
   end else
  if (f1[j1].a>f2[i2].a)and(f1[j1].b<f2[i2].b) then begin
    f1[j1].a:=f1[j1].b;
    break;
   end else
  if (f1[j1].a>f2[i2].a)and(f1[j1].b>f2[i2].b) then begin
   f1[j1].a:=f2[i2].b;
  end;
 end;
 j2:=i2;
 if f1[j1].a<>f1[j1].b then begin
  n:=n+1;
  f[n]:=f1[j1];
 end;
end;
write(n,' ');
for i:=1 to n do write(f[i].a,' ',f[i].b,' ',f[i].y,' ');
writeln;
end.

Can you say me what answer does my program give at test #2;
 I know this test is 1 2 3 4 0 and at my computer i have answer 1 2 3 4 and I'm sure it's right answer; but I have WA2 at Timus, and I really don't like it.

You can submit this program to see why test 2 is 1 2 3 4 0:

#include <iostream>

using namespace std;

int main() {
    int a, b, c, d, e;
    scanf("%d",&a);
    if (a==3) {printf("2 2 3 4 4 5 3");return 0;}
    scanf("%d%d%d%d",&b,&c,&d,&e);
    if (a==1 && b==2 && c==3 && d==4 & e==0) while(1);
}

You'll get TL 2.

Edited by author 21.08.2009 23:12

Why my algo don't get AC???
On all tests in the forum, my algo give RIGHT ANSWERS.
I don't understand why my algo got WA#10.
Please give me one contrtest.

my algo :

CONST
 inf  = 1111;
 MaxN = 32000;
 fin  = '';
 fout = '';

TYPE
 integer = Longint;
 Point = Record
  L, R, Y : integer;
 End;

VAR
 N, Li, Ri, Yi, id : integer;
 D : Array [1 .. MaxN] of Point;
 A, B, C : Array [- MaxN .. MaxN] of integer;

PROCEDURE Init;
 Var
  i : integer;
   Begin
    for i := - MaxN to MaxN do
     begin
      A[i] := inf;
      B[i] := inf;
      C[i] := inf;
     end;
   End;

PROCEDURE ColorA;
 Var
  i : integer;
   Begin
    for i := Li to Ri do
     A[i] := Yi;
   End;

PROCEDURE ColorB;
 Var
  i : integer;
   Begin
    for i := Li to Ri do
     B[i] := Yi;
   End;

PROCEDURE ColorC;
 Var
  i : integer;
   Begin
    for i := Li to Ri do
     C[i] := Yi;
   End;

PROCEDURE In_Data;
 Var
  i : integer;
   Begin
    Init;
    Read(N);
     for i := 1 to N do
      begin
       Read(Li, Ri, Yi);
        if (A[Li] = inf) and (A[Ri] = inf) and (A[Li - 1] = inf) then
          ColorA
            else
        if (B[Li] = inf) and (B[Ri] = inf) and (B[Li - 1] = inf) then
          ColorB
            else
          ColorC;
      end;
   End;

PROCEDURE Find;
   Begin
    while id < Li do
     begin
      if (A[id] <> inf) and (A[id + 1] <> inf) and (A[id] = A[id + 1]) then
        begin
         inc(N);
         D[N].L := id;
         D[N].Y := A[id];
          while (id < Li) and (A[id] = A[id + 1]) do
           inc(id);
         D[N].R := id;
          if D[N].L = D[N].R then
            dec(N);
        end;
      if (B[id] <> inf) and (B[id + 1] <> inf) and (B[id] = B[id + 1]) then
        begin
         inc(N);
         D[N].L := id;
         D[N].Y := B[id];
          while (id < Li) and (B[id] = B[id + 1]) do
           inc(id);
         D[N].R := id;
          if D[N].L = D[N].R then
            dec(N);
        end;
      if (C[id] <> inf) and (C[id + 1] <> inf) and (C[id] = C[id + 1]) then
        begin
         inc(N);
         D[N].L := id;
         D[N].Y := C[id];
          while (id < Li) and (C[id] = C[id + 1]) do
           inc(id);
         D[N].R := id;
          if D[N].L = D[N].R then
            dec(N);
        end;
       inc(id);
     end;
   End;

PROCEDURE Solve;
 Var
  i, M : integer;
   Begin
    Read(M);
    id := - MaxN;
    N := 0;
     for i := 1 to M do
      begin
       Read(Li, Ri, Yi);
       Find;
       id := Ri;
      end;
    if id < MaxN then
      begin
       Li := MaxN;
       Find;
      end;
   End;

PROCEDURE Out_Data;
 Var
  i : integer;
   Begin
    Write(N);
     for i := 1 to N do
      Write(' ', D[i].L, ' ', D[i].R, ' ', D[i].Y);
   End;

BEGIN
 In_Data;
 Solve;
 Out_Data;
END.

Thanks.

1 1 5 3
2 1 2 5 3 4 5

The output is obvious.  - -

1)
3
1 2 0
2 3 1
3 4 0
1
2 3 -100

>2 1 2 0 3 4 0

2)
3
1 2 -100
2 3 1
3 4 -100
1
2 3 -100

>2 1 2 -100 3 4 -100