Instantly share code, notes, and snippets.

# yurahuna/aoj2152.cpp Created Oct 25, 2016

What would you like to do?
 #include 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 Pii; typedef tuple TUPLE; typedef vector vi; typedef vector vvi; typedef vector vvvi; typedef vector vp; typedef vector> 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 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; } }