ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1003. Parity

WHI WA ON P1003
Posted by I am david. Tabo. 6 Nov 2002 22:28
type
  answer=record
    range_from,range_to:longint;
    parity:boolean;
end;

var answers:array[1..5000] of answer;

procedure exchange(p,q:word);
var r:answer;
 begin
  r:=answers[p];
  answers[p]:=answers[q];
  answers[q]:=r
 end;

var contradiction:boolean;
    length:longint;
    answers_given:word;
    answers_read:word;
    answers_stored:word;
    i:word;
    s:string;
begin
 readln(length);
 readln(answers_given);
 contradiction:=false;
 answers_read:=0; answers_stored:=0;
 if answers_given<>0 then
   repeat
     inc(answers_read);
     inc(answers_stored);
     readln(answers[answers_stored].range_from,answers
[answers_stored].range_to,s);
     answers[answers_stored].parity:=s=' odd';
     i:=answers_stored-1;
     while (i>0) and (answers[i].range_from>=answers
[answers_stored].range_from) do
       dec(i);
     inc(i);
     while (i<>answers_stored) and (answers[i].range_from=answers
[answers_stored].range_from) do
       begin
         if answers[i].range_to>answers[answers_stored].range_to then
           exchange(i,answers_stored);
         if answers[i].range_to=answers[answers_stored].range_to then
           begin
             contradiction:=answers[i].parity<>answers
[answers_stored].parity;
             dec(answers_stored);
             i:=answers_stored;
           end
         else
           begin
             answers[answers_stored].range_from:=answers
[i].range_to+1;
             answers[answers_stored].parity:=answers[i].parity xor
answers[answers_stored].parity;
           end;
         while (i<answers_stored) and (answers[i].range_from<answers
[answers_stored].range_from) do
           inc(i);
       end;
    while (i<>answers_stored) do
      begin
        exchange(i,answers_stored);
        inc(i)
      end
   until contradiction or (answers_read=answers_given);
 {Writing results to the output file}
 if contradiction then
   writeln(answers_read-1)
 else
   writeln(answers_read);
end.