This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#define PROBLEM \ "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2152&lang=jp" #include <iostream> #include <map> #include <vector> #include "data_structure/section_set.hpp" using i64 = std::int64_t; int main() { int n; while (std::cin >> n, !(n == 0)) { ebi::section_set<i64> used, noused; noused.insert(0, 1e9 + 7); std::map<i64, std::vector<std::pair<i64, i64>>> map; std::map<i64, i64> vmap; vmap[std::numeric_limits<i64>::max()] = -1; while (n--) { char c; i64 idx; std::cin >> c >> idx; if (c == 'W') { i64 s; std::cin >> s; while (s > 0) { auto [l, r] = noused.lower_bound(0); i64 w = std::min(r - l, s); used.insert(l, l + w); map[idx].emplace_back(l, l + w); vmap[l] = idx; noused.erase(l, r); if (w != r - l) { noused.insert(l + w, r); } s -= w; } } else if (c == 'D') { for (auto [l, r] : map[idx]) { assert(used.find(l, r)); used.erase(l, r); vmap.erase(l); noused.insert(l, r); } map.erase(idx); } else { if (!used.find(idx)) { std::cout << "-1\n"; continue; } auto itr = std::prev(vmap.upper_bound(idx)); std::cout << itr->second << '\n'; } } std::cout << '\n'; } }
#line 1 "test/aoj/aoj_2152.test.cpp" #define PROBLEM \ "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2152&lang=jp" #include <iostream> #include <map> #include <vector> #line 2 "data_structure/section_set.hpp" #include <cassert> #include <limits> #include <set> namespace ebi { template <class T> struct section_set { private: std::set<std::pair<T, T>> set; public: section_set() { set.insert( {std::numeric_limits<T>::min(), std::numeric_limits<T>::min()}); set.insert( {std::numeric_limits<T>::max(), std::numeric_limits<T>::max()}); } std::set<std::pair<T, T>> sections() const { return set; } // [l, r)を追加 void insert(T l, T r) { auto itr = std::prev(set.lower_bound({l, std::numeric_limits<T>::min()})); if (l <= itr->second) { assert(itr->first <= l); l = itr->first; r = std::max(r, itr->second); set.erase(itr); } itr = set.lower_bound({l, std::numeric_limits<T>::min()}); while (itr->first <= r) { assert(l <= itr->first); r = std::max(r, itr->second); itr = set.erase(itr); } set.insert({l, r}); return; } // 集合内の[l, r)に含まれている要素を削除 void erase(T l, T r) { auto itr = std::prev(set.lower_bound({l, std::numeric_limits<T>::min()})); if (l < itr->second) { assert(itr->first < l); set.insert({itr->first, l}); if (r < itr->second) { set.insert({r, itr->second}); } set.erase(itr); } itr = set.lower_bound({l, std::numeric_limits<T>::min()}); while (itr->first < r) { if (itr->second <= r) { itr = set.erase(itr); } else { set.insert({r, itr->second}); set.erase(itr); break; } } return; } bool find(T x) const { auto itr = std::prev(set.upper_bound({x, std::numeric_limits<T>::max()})); if (x < itr->second) { assert(itr->first <= x); return true; } else { return false; } } bool find(T l, T r) const { auto itr = std::prev(set.upper_bound({l, std::numeric_limits<T>::max()})); if (r <= itr->second) { assert(itr->first <= l); return true; } else { return false; } } std::pair<T, T> belong(T x) const { auto itr = std::prev(set.upper_bound({x, std::numeric_limits<T>::max()})); if (x < itr->second) { assert(itr->first <= x); return *itr; } else { return {0, 0}; } } std::pair<T, T> lower_bound(T l) const { return *set.lower_bound({l, std::numeric_limits<T>::min()}); } }; } // namespace ebi #line 9 "test/aoj/aoj_2152.test.cpp" using i64 = std::int64_t; int main() { int n; while (std::cin >> n, !(n == 0)) { ebi::section_set<i64> used, noused; noused.insert(0, 1e9 + 7); std::map<i64, std::vector<std::pair<i64, i64>>> map; std::map<i64, i64> vmap; vmap[std::numeric_limits<i64>::max()] = -1; while (n--) { char c; i64 idx; std::cin >> c >> idx; if (c == 'W') { i64 s; std::cin >> s; while (s > 0) { auto [l, r] = noused.lower_bound(0); i64 w = std::min(r - l, s); used.insert(l, l + w); map[idx].emplace_back(l, l + w); vmap[l] = idx; noused.erase(l, r); if (w != r - l) { noused.insert(l + w, r); } s -= w; } } else if (c == 'D') { for (auto [l, r] : map[idx]) { assert(used.find(l, r)); used.erase(l, r); vmap.erase(l); noused.insert(l, r); } map.erase(idx); } else { if (!used.find(idx)) { std::cout << "-1\n"; continue; } auto itr = std::prev(vmap.upper_bound(idx)); std::cout << itr->second << '\n'; } } std::cout << '\n'; } }