icpc_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ebi-fly13/icpc_library

:heavy_check_mark: test/data_structure/aoj_2152.test.cpp

Depends on

Code

#define PROBLEM \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2152&lang=jp"

#include "../../data_structure/section_set.hpp"
#include "../../template/template.hpp"

using i64 = std::int64_t;

int main() {
    int n;
    while (std::cin >> n, !(n == 0)) {
        lib::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/data_structure/aoj_2152.test.cpp"
#define PROBLEM \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2152&lang=jp"

#line 2 "data_structure/section_set.hpp"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 4 "data_structure/section_set.hpp"

namespace lib {

template <class T> struct section_set {
  private:
    std::set<std::pair<T, T>> st;

  public:
    section_set() {
        st.insert(
            {std::numeric_limits<T>::min(), std::numeric_limits<T>::min()});
        st.insert(
            {std::numeric_limits<T>::max(), std::numeric_limits<T>::max()});
    }

    std::set<std::pair<T, T>> sections() const {
        return st;
    }

    // [l, r)を追加
    void insert(T l, T r) {
        auto itr =
            std::prev(st.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);
            st.erase(itr);
        }
        itr = st.lower_bound({l, std::numeric_limits<T>::min()});
        while (itr->first <= r) {
            assert(l <= itr->first);
            r = std::max(r, itr->second);
            itr = st.erase(itr);
        }
        st.insert({l, r});
        return;
    }

    // 集合内の[l, r)に含まれている要素を削除
    void erase(T l, T r) {
        auto itr =
            std::prev(st.lower_bound({l, std::numeric_limits<T>::min()}));
        if (l < itr->second) {
            assert(itr->first < l);
            st.insert({itr->first, l});
            if (r < itr->second) {
                st.insert({r, itr->second});
            }
            st.erase(itr);
        }
        itr = st.lower_bound({l, std::numeric_limits<T>::min()});
        while (itr->first < r) {
            if (itr->second <= r) {
                itr = st.erase(itr);
            } else {
                st.insert({r, itr->second});
                st.erase(itr);
                break;
            }
        }
        return;
    }

    bool find(T x) const {
        auto itr =
            std::prev(st.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(st.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(st.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 *st.lower_bound({l, std::numeric_limits<T>::min()});
    }
};

}  // namespace lib
#line 6 "test/data_structure/aoj_2152.test.cpp"

using i64 = std::int64_t;

int main() {
    int n;
    while (std::cin >> n, !(n == 0)) {
        lib::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';
    }
}
Back to top page