这题灵活运用了std::map
- 给出一个长度无限的数列,初始全部为零,有三种操作:
- 增加操作:给下标为 t 的数加 c 。特别注意,如果在下标 [t-30,t+30] 内有不为零的数,增加操作无效。
- 削减操作:让数列中下标最小的不为零数变为零。
- 查询操作:查询数列中下标为 tt 的数字是多少。
std::map
tutorial:无脑维护
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define _rep(n, a, b) for (ll n = (a); n <= (b); ++n)
#define _rev(n, a, b) for (ll n = (a); n >= (b); --n)
#define _for(n, a, b) for (ll n = (a); n < (b); ++n)
#define _rof(n, a, b) for (ll n = (a); n > (b); --n)
#define oo 0x3f3f3f3f3f3f
#define ll long long
#define db double
#define eps 1e-6
#define bin(x) cout << bitset<10>(x) << endl;
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define mp(a, b) make_pair(a, b)
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
#define pdd pair<db, db>
#define pi acos(-1.0)
const ll maxn = 3e5 + 10;
const ll mod = 1e9 + 7;
map<ll, ll> q;
signed main()
{
ll n;
cin >> n;
_rep(i, 1, n)
{
ll fir, sec = oo;
cin >> fir;
char ch = getchar();
if (ch != '\n')
{ //两个数
cin >> sec;
}
if (fir < 0)
{
if (q.empty())
cout << "skipped" << endl;
else
{
cout << q.begin()->second << endl;
q.erase(q.begin());
}
}
else if (sec == oo)
{
if(q.find(fir) != q.end())cout << q[fir] << endl;
else cout << 0 << endl;
}
else if (sec != oo)
{
bool add = 1;
_rep(i, fir - 30, fir + 30)
{
if (q.find(i) != q.end()){
add = 0;
break;
}
}
if(add){
q[fir] = sec;
}
}
}
}