Create a gist now

Instantly share code, notes, and snippets.

#include <bits/stdc++.h>
using namespace std;
// #define int long long // <-----!!!!!!!!!!!!!!!!!!!
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) for(auto x : v){cout << x << " ";} cout << endl
#define printVS(vs) for(auto x : vs){cout << x << endl;}
#define printVV(vv) for(auto v : vv){for(auto&& x : v){cout << x << " ";}cout << endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto p : vp) printP(p);
typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
typedef vector<vector<int>> Graph;
// const int inf = 1e9;
const int inf = 2e9;
const int mod = 1e9 + 7;
struct Range {
int l, r; // [l, r)
int no;
Range(){}
Range(int _l, int _r, int _no) : l(_l), r(_r), no(_no) {}
bool operator<( const Range& right ) const {
if (l != right.l) return l < right.l;
if (r != right.r) return r < right.r;
return no < right.no;
}
void print() {
cout << l << " " << r << " " << no << endl;
}
};
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n;
while (cin >> n, n) {
set<Range> st;
st.insert(Range(-inf, 0, -1));
st.insert(Range(inf - 1, inf, -1));
rep(i, n) {
char mode;
cin >> mode;
if (mode == 'W') {
int no, len;
cin >> no >> len;
for (auto it = st.begin(); next(it) != st.end() && len > 0; it++) {
int len_here = min(len, next(it)->l - it->r);
if (len_here > 0) {
it = st.insert(Range(it->r, it->r + len_here, no)).first;
len -= len_here;
}
}
} else if (mode == 'D') {
int no;
cin >> no;
for (auto it = st.begin(); it != st.end(); ) {
if (it->no == no) {
it = st.erase(it);
} else {
it++;
}
}
} else if (mode == 'R') {
int pos;
cin >> pos;
auto it = st.upper_bound(Range(pos, inf, inf));
it--;
cout << (pos < it->r ? it->no : -1) << endl;
}
}
// end of data
cout << endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment