test/DataStructure/interval-set/yukicoder-3017.cpp

• View this file on GitHub
• Last update: 2025-12-11 22:28:56+09:00
• Problem: https://yukicoder.me/problems/no/3017

Depends on

• Interval Set (DataStructure/interval_set.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/3017

#include "DataStructure/interval_set.hpp"
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N;
    cin >> N;

    IntervalSet<int> interval_set;

    for (int i = 0; i < N; i++)
    {
        int H;
        cin >> H;
        if (i % 2 == 0)
        {
            interval_set.add_interval(0, H);
        }
        else
        {
            interval_set.erase_interval(0, H);
        }
        cout << interval_set.get_sum_lentgth() << endl;
    }

    return 0;
}

#line 1 "test/DataStructure/interval-set/yukicoder-3017.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/3017

#line 1 "DataStructure/interval_set.hpp"
#include <bits/stdc++.h>
using namespace std;

// contains
// find_intervalのpublic化
// 次の区間までの

template <typename T, typename Compare = std::less<T>>
    requires std::strict_weak_order<Compare, T, T>
class IntervalSet
{
private:
    // すべての区間長の合計
    T sum_length = 0;

    // 互いに交差しない半開区間 [first, second) の集合
    set<pair<T, T>> intervals;

    // 点 x を含む区間のイテレータ（なければ end）
    typename set<pair<T, T>>::const_iterator
    find_interval(const T &x) const
    {
        // first >= x となる最初の区間
        auto itr = intervals.lower_bound({x, x});

        // ひとつ左だけ、x を含みうる
        if (itr != intervals.begin())
        {
            auto prev_itr = prev(itr);
            if (prev_itr->first <= x && x < prev_itr->second)
                return prev_itr;
        }

        // ぴったり x から始まる区間
        if (itr != intervals.end() && itr->first <= x && x < itr->second)
            return itr;

        return intervals.end();
    }

public:
    IntervalSet() {}

    // [L, R) を追加し、必要なら隣接区間とマージする
    pair<T, T> add_interval(const T &L, const T &R)
    {
        return add_interval({L, R});
    }

    // [L, R) を追加し、必要なら隣接区間とマージする
    pair<T, T> add_interval(const pair<T, T> &LR)
    {
        assert(LR.first < LR.second);

        auto [l, r] = LR;

        // first >= l となる最初の区間
        auto itr = intervals.lower_bound(LR);

        // 左側に 1 つだけ重なりうる区間を見る
        if (itr != intervals.begin())
        {
            auto prev_itr = prev(itr);
            if (prev_itr->second >= l)
            {
                l = min(l, prev_itr->first);
                r = max(r, prev_itr->second);

                sum_length -= abs(prev_itr->second - prev_itr->first);
                itr = intervals.erase(prev_itr);
            }
        }

        // 先頭が r 以下の区間をすべてマージ
        while (itr != intervals.end() && itr->first <= r)
        {
            l = min(l, itr->first);
            r = max(r, itr->second);

            sum_length -= abs(itr->second - itr->first);
            itr = intervals.erase(itr);
        }

        intervals.insert({l, r});
        sum_length += abs(r - l);

        return {l, r};
    }

    // 区間集合から [L, R) を削除（集合としての差）
    void erase_interval(const T &L, const T &R)
    {
        erase_interval({L, R});
    }

    // 区間集合から [L, R) を削除（集合としての差）
    void erase_interval(const std::pair<T, T> &LR)
    {
        assert(LR.first < LR.second);

        const auto [l, r] = LR;
        if (intervals.empty())
            return;

        // first >= l となる最初の区間
        auto itr = intervals.lower_bound(LR);

        // 左側に 1 つだけ、[l, r) と交差しうる区間を見る
        if (itr != intervals.begin())
        {
            auto prev_itr = prev(itr);
            const auto [a, b] = *prev_itr;

            // [a, b) と [l, r) が交差
            if (b > l && a < r)
            {
                itr = intervals.erase(prev_itr);
                sum_length -= abs(b - a);

                if (a < l)
                {
                    sum_length += abs(l - a);
                    intervals.insert({a, l});
                }
                if (r < b)
                {
                    sum_length += abs(b - r);
                    intervals.insert({r, b});
                }
            }
        }

        // ここから先は first >= l が保証されている
        while (itr != intervals.end())
        {
            const auto [a, b] = *itr;

            if (a >= r)
                break; // これ以降は交差しない

            if (b <= r)
            {
                // 完全に [l, r) に含まれる区間
                itr = intervals.erase(itr);
                sum_length -= abs(b - a);
            }
            else
            {
                // a < r < b →右側 [r, b) だけ残す
                intervals.erase(itr);
                intervals.insert({r, b});
                sum_length -= abs(b - a);
                sum_length += abs(b - r);
                break;
            }
        }
    }

    // u と v が同じ区間に属するか
    bool same(T u, T v) const
    {
        if (intervals.empty())
            return false;

        if (v < u)
            swap(u, v);

        auto itr = find_interval(u);
        if (itr == intervals.end())
            return false;

        return v < itr->second;
    }

    // u が属する区間の長さ（なければ 0）
    T length(const T &u) const
    {
        auto itr = find_interval(u);
        if (itr == intervals.end())
            return T(0);
        return itr->second - itr->first;
    }

    // すべての区間長の合計
    T get_sum_lentgth() const
    {
        return sum_length;
    }

    void print() const
    {
        for (auto [l, r] : intervals)
        {
            cout << "[" << l << ", " << r << ") ";
        }
        cout << '\n';
    }
};
#line 5 "test/DataStructure/interval-set/yukicoder-3017.cpp"

using namespace std;

int main()
{
    int N;
    cin >> N;

    IntervalSet<int> interval_set;

    for (int i = 0; i < N; i++)
    {
        int H;
        cin >> H;
        if (i % 2 == 0)
        {
            interval_set.add_interval(0, H);
        }
        else
        {
            interval_set.erase_interval(0, H);
        }
        cout << interval_set.get_sum_lentgth() << endl;
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	01_sample_01.txt	AC	5 ms	3 MB
g++	02_random_01.txt	AC	247 ms	3 MB
g++	02_random_02.txt	AC	245 ms	3 MB
g++	02_random_03.txt	AC	253 ms	3 MB
g++	02_random_04.txt	AC	264 ms	3 MB
g++	02_random_05.txt	AC	255 ms	3 MB
g++	02_random_06.txt	AC	266 ms	3 MB
g++	02_random_07.txt	AC	244 ms	3 MB
g++	02_random_08.txt	AC	254 ms	3 MB
g++	02_random_09.txt	AC	292 ms	3 MB
g++	02_random_10.txt	AC	259 ms	3 MB
g++	02_random_11.txt	AC	261 ms	3 MB
g++	02_random_12.txt	AC	249 ms	3 MB
g++	02_random_13.txt	AC	274 ms	3 MB
g++	02_random_14.txt	AC	275 ms	3 MB
g++	02_random_15.txt	AC	254 ms	3 MB
g++	02_random_16.txt	AC	311 ms	3 MB
g++	02_random_17.txt	AC	277 ms	3 MB
g++	02_random_18.txt	AC	268 ms	3 MB
g++	02_random_19.txt	AC	322 ms	3 MB
g++	02_random_20.txt	AC	245 ms	3 MB
g++	02_random_21.txt	AC	314 ms	3 MB
g++	02_random_22.txt	AC	267 ms	3 MB
g++	02_random_23.txt	AC	285 ms	3 MB
g++	02_random_24.txt	AC	305 ms	3 MB
g++	02_random_25.txt	AC	265 ms	3 MB
g++	02_random_26.txt	AC	248 ms	3 MB
g++	02_random_27.txt	AC	261 ms	3 MB
g++	02_random_28.txt	AC	253 ms	3 MB
g++	02_random_29.txt	AC	247 ms	3 MB
g++	02_random_30.txt	AC	264 ms	3 MB
g++	02_random_31.txt	AC	55 ms	3 MB
g++	02_random_32.txt	AC	180 ms	3 MB
g++	02_random_33.txt	AC	240 ms	3 MB
g++	02_random_34.txt	AC	162 ms	3 MB
g++	02_random_35.txt	AC	172 ms	3 MB
g++	02_random_36.txt	AC	53 ms	3 MB
g++	02_random_37.txt	AC	135 ms	3 MB
g++	02_random_38.txt	AC	186 ms	3 MB
g++	02_random_39.txt	AC	31 ms	3 MB
g++	02_random_40.txt	AC	235 ms	3 MB
g++	03_hand_1.txt	AC	6 ms	3 MB
g++	03_hand_10.txt	AC	243 ms	3 MB
g++	03_hand_11.txt	AC	282 ms	6 MB
g++	03_hand_12.txt	AC	243 ms	3 MB
g++	03_hand_13.txt	AC	269 ms	6 MB
g++	03_hand_14.txt	AC	241 ms	3 MB
g++	03_hand_15.txt	AC	265 ms	6 MB
g++	03_hand_2.txt	AC	5 ms	3 MB
g++	03_hand_3.txt	AC	4 ms	3 MB
g++	03_hand_4.txt	AC	199 ms	3 MB
g++	03_hand_5.txt	AC	246 ms	3 MB
g++	03_hand_6.txt	AC	244 ms	3 MB
g++	03_hand_7.txt	AC	268 ms	6 MB
g++	03_hand_8.txt	AC	238 ms	3 MB
g++	03_hand_9.txt	AC	266 ms	6 MB

Back to top page