用链表维护未入住的房间，连续的合并成一个节点
写起来确实有点麻烦
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstdarg>
#include <climits>

#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>

#include <iostream>
#include <sstream>

#include <string>
#include <algorithm>
#include <utility>
#include <complex>
#include <functional>

using namespace std;

typedef long long int64;

const int inf = 0x3f3f3f3f;
const int64 inf64 = 0x3f3f3f3f3f3f3f3fLL;

template <class Tp>
Tp vaMax(int n, Tp v1, ...)
{
    va_list ap;
    va_start(ap, v1);
    Tp res = v1;
    for (int i = 1; i < n; i++)
    {
        Tp temp = va_arg(ap, Tp);
        if (temp > res) res = temp;
    }
    va_end(ap);
    return res;
}

template <class Tp>
Tp vaMin(int n, Tp v1, ...)
{
    va_list ap;
    va_start(ap, v1);
    Tp res = v1;
    for (int i = 1; i < n; i++)
    {
        Tp temp = va_arg(ap, Tp);
        if (temp < res) res = temp;
    }
    va_end(ap);
    return res;
}

const int maxN = 5e4 + 5;

struct Node
{
    int first;
    int len;

    Node(int f, int l): first(f), len(l) {}
};
list<Node> vacantList;

int N, M;

void init()
{
    vacantList.push_back(Node(1, N));
}

typedef list<Node>::iterator Iter;

int checkin(int d)
{
    Iter it = vacantList.begin();
    for (; it != vacantList.end(); ++it)
    {
        if (it->len >= d)
            break; // found
    }
    if (it == vacantList.end())
        return 0; // not found
    if (it->len > d)
        vacantList.insert(it, Node(it->first + d, it->len - d)); // rest part

    int res = it->first;
    vacantList.erase(it);
    return res;
}

void merge(Iter it)
{
    int ed = it->first + it->len - 1; // end position of new range
    Iter last = it; 
    for (++last; last != vacantList.end(); ++last)
    {
        if (last->first > ed + 1)
            break; // can't merge anymore
        ed = max(ed, last->first + last->len - 1);
    }
    vacantList.insert(it, Node(it->first, ed - it->first + 1));
    vacantList.erase(it, last); // clear the merged nodes
}

void checkout(int x, int d)
{
    Iter it = vacantList.begin();
    for (; it != vacantList.end(); ++it)
    {
        if (it->first > x)
        {
            if (x + d >= it->first) // x + d - 1 >= it->first - 1
            {
                it->len += (it->first - x);
                it->first = x;
                it->len = max(it->len, d);
                merge(it);
            }
            else 
            {
                vacantList.insert(it, Node(x, d));
            }
            return;
        }
        else if (x >= it->first && x <= it->first + it->len) // x <= (first + len - 1) + 1
        {
            it->len = max(it->len, d + x - it->first);
            merge(it);
            return;
        }
    }
    vacantList.push_back(Node(x, d)); // it == end()
}

int main()
{
    scanf("%d%d", &N, &M);
    init();
    while (M--)
    {
        int cmd, x, d;
        scanf("%d", &cmd);
        if (cmd == 1)
        {
            scanf("%d", &d);
            printf("%d\n", checkin(d));
        }
        else
        {
            scanf("%d%d", &x, &d);
            checkout(x, d);
        }
    }
    return 0;
}