UVA_10901_Ferry_Loading_III

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <sstream>
#include <stdlib.h>
#include <cmath>
#define FOR(i,A) for(typeof (A).begin() i = (A).begin() ; i != (A).end() ; i++)
#define debug( x ) cout << #x << " = " << x << endl
#define clr(v,x) memset( v, x , sizeof v )
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define TAM 110

using namespace std;

typedef pair<int,int> ii ;
typedef long long ll ;
typedef long double ld ;
typedef pair<int,ii> pii ;

int main() {
 int c, n, t, m, val, kr = 0, kl = 0, cap = 0, time = 0, cont = 0;
 char direccion[20];
 scanf("%d", &c);
 for (int k = 0; k < c; k++) {
  queue<int> left, right;
  scanf("%d %d %d", &n, &t, &m);
  kr = kl = 0;
  vector<int> posiciones(m);
  cont = 0;
  for (int i = 0; i < m; i++) {
   scanf("%d %s", &val, direccion);
   if(strcmp(direccion,"left") == 0)
    left.push(val), kl++,posiciones[cont++] = 0;
   else
    right.push(val), kr++,posiciones[cont++] = 1;
  }
  vector<int> listaL(kl), listaR(kr);
  kl = kr = cap = time = 0;
  string ini = "left";
  while (!left.empty() || !right.empty()) {
   if (!left.empty() && !right.empty()) {
    if(left.front() > time && right.front() > time) {
     if(left.front() > right.front()) {
      time += right.front() - time;
      if(ini == "left") time += t;
      ini = "right";
     }
     else {
      time += left.front() - time;
      if(ini == "right") time += t;
      ini = "left";
     }
    }
   }
   else {
    if (left.empty()) {
     if (right.front() > time) {
      time += right.front() - time;
      if(ini == "left") time += t;
      ini = "right";
     }
    }
    else {
     if (left.front() > time) {
      time += left.front() - time;
      if(ini == "right") time += t;
      ini = "left";
     }
    }
   }
   if (ini == "left") {
    cap = 0;
    while (cap < n && !left.empty() && left.front() <= time) {
     //printf("left %d\n", time + t);
     listaL[kl++] = time + t;
     left.pop();
     cap++;
    }
    time += t;
    ini = "right";
   }
   else {
    cap = 0;
    while (cap < n && !right.empty() && right.front() <= time) {
     //printf("right %d\n", time + t);
     listaR[kr++] = time + t;
     right.pop();
     cap++;
    }
    time += t;
    ini = "left";
   }
  }
  kl = kr = 0;
  for (int i = 0; i < m; i++) {
   if (!posiciones[i])
    printf("%d\n", listaL[kl++]);
   else
    printf("%d\n", listaR[kr++]);
  }
  if(k + 1 != c) printf("\n");
 }
 return 0;
}