people, if you have some idea about solution of problem, please write.
i've tried to generate all possible intervals, but it failed because
of memory limit exceed.

> people, if you have some idea about solution of problem, please
write.
> i've tried to generate all possible intervals, but it failed
because
> of memory limit exceed.

>

> people, if you have some idea about solution of problem, please write.
> i've tried to generate all possible intervals, but it failed because
> of memory limit exceed.

u don't have to generate all possible,keep the smallest one
I tried to solve it with doubly linked list but i always got CRASH
So at last i use array to keep the intervals and got AC
in 0.941 sec 86K (bad time but at least AC)

( i use insertion sort to sort the interval
everytime i update cuz i think it's the fastest na)

So may you say that how you do insertion?
i mean but which value of interval?
such as first limit or something else???
Best
Aidin

i sort it by the first
it help u to update the intervals
Anyway my PROG's below
don't see if u don't want :)
GooD LucK,
TheBlaNK
















#include <stdio.h>
#include <stdlib.h>
#define MAX 5005
FILE *fp,*fx;
struct node
{
 long b,e;
 char st;
};
struct node arr[MAX];
long many,n;

long insert(long b,long e,long s)
{
 long tmpb,tmpe,j,i,tmpst;
 for(i=0;i<many&&b>=arr[i].b;i++)
   {
    if(arr[i].b==b)
      {
    if(arr[i].e<e) { b=arr[i].e+1; s=(arr[i].st)^s; }
    else if(arr[i].e>e) { tmpst=s; s=(arr[i].st)^s; b=e+1;
             e=arr[i].e; arr[i].e=b-1; arr
[i].st=tmpst; }
    else if(arr[i].st==s) return 0;
    else return 1;
      }
   }
 for(i=0;i<many;i++)
   {
    if(arr[i].e==e)
      {
    if(arr[i].b>b) { e=arr[i].b-1; s=(arr[i].st)^s; }
    else if(arr[i].b<b) { tmpst=s; s=(arr[i].st)^s; e=b-1;
              b=arr[i].b; arr[i].b=e+1; arr
[i].st=tmpst; }
    else if(arr[i].st==s) return 0;
    else return 1;
      }
   }
 arr[many].b=b; arr[many].e=e; arr[many].st=s;
 many++;
 for(i=1;i<many;i++)
  {
   tmpb=arr[i].b; tmpe=arr[i].e; tmpst=arr[i].st;
   for(j=i-1;j>=0&&arr[j].b>tmpb;j--)
    { arr[j+1].b=arr[j].b; arr[j+1].e=arr[j].e; arr[j+1].st=arr[j].st;
    }
   arr[j+1].b=tmpb; arr[j+1].e=tmpe; arr[j+1].st=tmpst;
  }
 return 0;
}

void input(void)
{
 long i,tmp,b,e,sta;
 char s[10];
 while(1)
  {
   fscanf(fp,"%ld",&tmp);
   if(tmp==-1) break;
   fscanf(fp,"%ld",&n);
   i=0;
   many=1;
   if(n>0)
     {
      fscanf(fp,"%ld %ld %s",&b,&e,s);
      if(s[0]=='e') sta=0; else sta=1;
      arr[0].b=b; arr[0].e=e; arr[0].st=sta;
      for(i=1;i<n;i++)
    {
     fscanf(fp,"%ld %ld %s",&b,&e,s);
     if(s[0]=='e') sta=0; else sta=1;
     if(insert(b,e,sta)) break;
    }
     }
   fprintf(fx,"%ld\n",i);
   for(i=i+1;i<n;i++) fscanf(fp,"%ld %ld %s",&b,&e,s);
  }
}

int main()
{
 fp=stdin; fx=stdout;
// fp=fopen("parity.i","r");  fx=fopen("1003-2.out","w");
  input();
// fclose(fp); fclose(fx);
 return 0;
}

i donno C at all :(((
Anyway
Thanks