AOJ 2152 : Restrictive Filesystem

問題リンク：Restrictive Filesystem | Aizu Online Judge

解法：
双方向連結リストを実装した

コード：

const uint64_t INF = 100000000000010;

struct List
{
  int identifier;
  uint64_t range[2];// [range[0],range[1]]
  bool hasNext,hasPrev;
  List *prev;
  List *next;
  List(int identifier=inf,uint64_t r1=INF,uint64_t r2=INF):identifier(identifier)
  {
    range[0] = r1, range[1] = r2;
    hasNext = hasPrev = false;
  }
};

int N,I,S,P;
char c;
List list;

void list_walk(List *l)
{
  cout << '[' << l->range[0] << "," << l->range[1] << " : " << l->identifier << "]";
  if(l->hasNext)list_walk(l->next);
}

void ddfs(List *l)
{
  if(l->hasNext)ddfs(l->next);
  if(l->hasPrev)delete l;
    
}

void init()
{
  if(list.hasNext)ddfs(&list);
  list.hasNext = true;
  list.hasPrev = false;
  list.range[0] = list.range[1] = -1;
  list.identifier = -1;
  list.next = new List;
  list.next->hasNext = false;
  list.next->hasPrev = true;
  list.next->range[0] = list.next->range[1] = INF;
  list.next->identifier = inf;
  list.next->prev = &list;
}

void dfsW(List *l)
{
  uint64_t v1 = l->range[1];
  uint64_t v2 = l->next->range[0];
  uint64_t diff = v2-v1-1;
  if(diff)
    {
      List *node = new List;
      node->identifier = I;
      node->hasNext = node->hasPrev = true;
      node->next = l->next;
      node->prev = l;
      l->next->prev = node;
      l->next = node;

      node->range[0] = v1+1;
      if(S <= diff)
	{
	  node->range[1] = node->range[0] + S - 1;
	  S = 0;
	}
      else if(S > diff)
	{
	  node->range[1] = node->range[0] + diff - 1;
	  S -= diff;
	}    
    }  
  if(S > 0)dfsW(l->next);
}

void compute_W()
{
  dfsW(&list);
}

void dfsD(List *l)
{
  if(l->identifier == I)
    {
      l->next->prev = l->prev;
      l->prev->next = l->next;
      delete l;
    }
  if(l->hasNext)dfsD(l->next);
}

void compute_D()
{
  dfsD(&list);
}

void dfsR(List *l)
{
  if(l->range[0] <= P && P <= l->range[1])
    {
      cout << l->identifier << endl;
    }
  else
    {
      if(l->hasNext)dfsR(l->next);
      else cout << -1 << endl;
    }
}

void compute_R()
{
  dfsR(&list);
}


int main()
{
  while(cin >> N,N)
    {

      init();
      rep(_,N)
	{
	  cin >> c;
	  if(c == 'W')cin >> I >> S,compute_W();
	  if(c == 'D')cin >> I,compute_D();
	  if(c == 'R')cin >> P,compute_R();
	}
      cout << endl;
    }
  return 0;
}