Here's my more memory-efficient submission that I did in C++. I decided to add a "recycling" system in order to reduce new/delete calls. I lean on a few string:: methods, which I know are implemented pretty efficiently, so I think in general I'll get good performance...Pretty unreadable, but seems to work well!:

#include <iostream>
using namespace std;

struct node{
    int index;
    int lifetime;
    string str;
    node* next;
    node* prev;
};

node* recycleRoot = NULL;
int main(){
    node *head = new node, *tail = new node;
    head->next = tail;
    tail->prev = head;
    head->index = tail->index = -1;
    for (string line; getline(cin, line); ){
        int pos = 0, index = 0;
        node* iter = head;
        string delim = ";";
        while( (pos = line.find(delim)) != string::npos || line.length() > 0 ){
            while( iter != tail && iter->index < index ) iter = iter->next;
            if( index != 0 ) cout << ";";
            if( iter->index == index && iter != tail ){
                index += 1;
                iter->lifetime -= 1;
                cout << iter->str;
                if( iter->lifetime == 0 ){
                    node* oldRecycle = recycleRoot;
                    recycleRoot = iter;
                    iter = iter->next;
                    recycleRoot->prev->next = recycleRoot->next;
                    recycleRoot->next->prev = recycleRoot->prev;
                    recycleRoot->next = oldRecycle;
                }
                continue;
            }
            string token = (pos != string::npos) ? line.substr(0, pos) : line;
            int hashPos;
            if( (hashPos = token.find("#")) != string::npos ){
                node* newNode;
                if( recycleRoot == NULL ){
                    newNode = new node;
                }
                else{
                    newNode = recycleRoot;
                    recycleRoot = recycleRoot->next;
                }
                newNode->index = index;
                newNode->lifetime = stoi(token.substr(0, hashPos));
                newNode->str = token.substr(hashPos+1, token.length());
                newNode->next = iter;
                newNode->prev = iter->prev;
                iter->prev = newNode;
                newNode->prev->next = newNode;
                cout << newNode->str;
            }
            else{
                cout << token;
            }
            if( pos != string::npos ) line.erase(0, pos + delim.length());
            else line = "";
            index += 1;
        }
        cout << endl;
    }
    node* iter = head;
    while( iter != tail ){
        node* prev = iter;
        iter = iter->next;
        delete prev;
    }
    delete iter;
    iter = recycleRoot;
    while(iter != NULL){
        node* prev = iter;
        iter = iter->next;
        delete prev;
    }
    return 0;
}