感觉没啥毛病，有的地方我也不太清楚那样写对不对..
by Rbu_nas @ 2019-11-05 07:13:13
$QAQ$
by leprechaun_kdl @ 2019-11-05 08:39:30
@[Rem°](/user/80358)
非常谢谢您当时愿意为我看这道题。
这是我退役以后看的第一道题，我对着CodeForces上的数据把它A了。
重点在它一开始就erase一个数，而且恰好是我规定的无内存状态。所以会把最开始的那总区间减去。
所以只要在erase前特判缩减的数是否小于等于0，如果小于等于0，就直接输出。
这是AC代码，只在原基础上加了一个if（在125行）
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;
#define ri register int
struct ODT
{
int l, r;
mutable int val, len;
ODT(int L = -1, int R = -1, int V = 0, int E = 0)
: l(L), r(R), val(V), len(E) {}
bool operator< (const ODT& x) const
{ return l < x.l;}
};
typedef set<ODT>::iterator IT;
set<ODT> nc;
int n, m, xth = 1;
char s[13];
inline void add_nc(int le)
{
int flag = 1;
IT it = nc.begin();
for ( ; it != nc.end(); ++it)
{
if (it->val != 0) continue;
if (it->len >= le)
{
int L = it->l, R = it->r, LE = it->len;
int pos = L + le;
nc.erase(it);
nc.insert(ODT(L, pos-1, xth, le));
if (pos <= R) nc.insert(ODT(pos, R, 0, LE-le));
flag = 0;
break;
}
}
if (flag) printf("NULL\n");
else printf("%d\n", xth), ++xth;
}
inline void erase_nc(int x)
{
int flag = 1;
IT it = nc.begin();
for ( ; it != nc.end(); ++it)
{
if (it->val == x)
{
it->val = 0;
flag = 0;
break;
}
}
if (flag) printf("ILLEGAL_ERASE_ARGUMENT\n");
else
{
if (it != nc.begin())
{
IT itn = it;
--it;
if (it->val == 0)
{
int L = it->l, R = itn->r, LE = it->len;
LE += itn->len;
nc.erase(it), nc.erase(itn);
itn = nc.insert(ODT(L, R, 0, LE)).first;
}
it = itn;
}
IT itn = it;
++it;
if (it != nc.end() && it->val == 0)
{
int L = itn->l, R = it->r, LE = it->len;
LE += itn->len;
nc.erase(it), nc.erase(itn);
nc.insert(ODT(L, R, 0, LE));
}
}
}
inline void defragment()
{
int LEO = 0;
IT it = nc.begin();
for ( ; it != nc.end(); )
{
if(it->val == 0)
{
LEO += it->len;
IT itn = it;
++itn;
nc.erase(it);
it = itn;
} else {
int L = it->l, R = it->r, V = it->val, LE = it->len;
L -= LEO, R -= LEO;
nc.erase(it);
it = nc.insert(ODT(L, R, V, LE)).first;
++it;
}
}
if(LEO) nc.insert(ODT(m-LEO+1, m, 0, LEO));
}
signed main()
{
scanf("%d%d", &n, &m);
nc.insert(ODT(1, m, 0, m));
for (ri i = 1; i <= n; ++i)
{
scanf("%s", s);
if (s[0] == 'a')
{
int x;
scanf("%d", &x);
add_nc(x);
} else if (s[0] == 'e') {
int x;
scanf("%d", &x);
if (x <= 0) {
printf("ILLEGAL_ERASE_ARGUMENT\n");
continue;
}
erase_nc(x);
} else if (s[0] == 'd') {
defragment();
}
}
return 0;
}
```
by leprechaun_kdl @ 2020-01-20 23:14:58