verify/yukicoder-2603.test.cpp

• View this file on GitHub
• Last update: 2026-05-29 20:48:10+09:00
• Problem: https://yukicoder.me/problems/no/2603

Depends on

• 区間インクリメント/デクリメントの最小回数（$\text{mod }m$） (other/minimum-mod-range-increment-decrement-operations.hpp)

Code

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

#include <iostream>
#include <vector>

#include "../other/minimum-mod-range-increment-decrement-operations.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    long long m;
    std::cin >> n >> m;

    std::vector<long long> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        std::cin >> b[i];
    }

    std::cout << minimum_mod_range_increment_decrement_operations(a, b, m)
              << '\n';
    return 0;
}

#line 1 "verify/yukicoder-2603.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/2603

#include <iostream>
#include <vector>

#line 1 "other/minimum-mod-range-increment-decrement-operations.hpp"



// 数列を mod m 上で見たとき、区間に +1 または -1 を加える操作の最小回数を求める。
// 区間に整数 x を加える操作の最小 sum |x| と同値である。
// a, b は同じ長さで、各要素は [0, m) を仮定する。
// T は 64 bit 整数型、m <= 10^9 を想定する。
// 計算量 O(N log N)。

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <type_traits>
#line 15 "other/minimum-mod-range-increment-decrement-operations.hpp"

template <class T>
T minimum_mod_range_increment_decrement_operations(std::vector<T> a,
                                                   std::vector<T> b, T m) {
    static_assert(std::is_integral_v<T>, "T must be integer.");
    static_assert(sizeof(T) >= sizeof(long long),
                  "T must be at least 64-bit integer type.");

    assert(a.size() == b.size());
    assert(m > 0);

    const std::size_t n = a.size();
    std::vector<T> differences;
    differences.reserve(n + 1);

    auto mod_difference = [m](T from, T to) -> T {
        return from <= to ? to - from : m - (from - to);
    };

    auto add_mod_difference = [m](std::size_t &quotient, T &remainder, T diff) {
        if (remainder >= m - diff) {
            remainder -= m - diff;
            ++quotient;
        } else {
            remainder += diff;
        }
    };

    T previous = 0;
    std::size_t negative_count = 0;
    T remainder = 0;
    for (std::size_t i = 0; i < n; ++i) {
        if constexpr (std::is_signed_v<T>) {
            assert(0 <= a[i]);
            assert(0 <= b[i]);
        }
        assert(a[i] < m);
        assert(b[i] < m);

        const T current = mod_difference(a[i], b[i]);
        const T diff = mod_difference(previous, current);
        differences.emplace_back(diff);
        add_mod_difference(negative_count, remainder, diff);
        previous = current;
    }

    const T last = mod_difference(previous, T(0));
    differences.emplace_back(last);
    add_mod_difference(negative_count, remainder, last);

    assert(remainder == 0);
    assert(negative_count <= n + 1);

    std::sort(differences.begin(), differences.end());

    const std::size_t keep_count = n + 1 - negative_count;
    T answer = 0;
    for (std::size_t i = 0; i < keep_count; ++i) {
        answer += differences[i];
    }
    return answer;
}


#line 7 "verify/yukicoder-2603.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    long long m;
    std::cin >> n >> m;

    std::vector<long long> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        std::cin >> b[i];
    }

    std::cout << minimum_mod_range_increment_decrement_operations(a, b, m)
              << '\n';
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	01_sample_01	AC	2 ms	3 MB
g++	01_sample_02	AC	2 ms	3 MB
g++	01_sample_03	AC	2 ms	3 MB
g++	4_small_case_1	AC	3 ms	4 MB
g++	4_small_case_10	AC	3 ms	4 MB
g++	4_small_case_2	AC	3 ms	3 MB
g++	4_small_case_3	AC	3 ms	4 MB
g++	4_small_case_4	AC	3 ms	4 MB
g++	4_small_case_5	AC	3 ms	3 MB
g++	4_small_case_6	AC	3 ms	4 MB
g++	4_small_case_7	AC	3 ms	4 MB
g++	4_small_case_8	AC	3 ms	4 MB
g++	4_small_case_9	AC	3 ms	4 MB
g++	5_max_case_1	AC	104 ms	11 MB
g++	5_max_case_10	AC	105 ms	11 MB
g++	5_max_case_2	AC	104 ms	11 MB
g++	5_max_case_3	AC	105 ms	11 MB
g++	5_max_case_4	AC	104 ms	11 MB
g++	5_max_case_5	AC	104 ms	11 MB
g++	5_max_case_6	AC	105 ms	11 MB
g++	5_max_case_7	AC	105 ms	11 MB
g++	5_max_case_8	AC	104 ms	11 MB
g++	5_max_case_9	AC	104 ms	11 MB
g++	6_zigzag_case_1	AC	99 ms	11 MB
g++	6_zigzag_case_10	AC	107 ms	11 MB
g++	6_zigzag_case_2	AC	101 ms	11 MB
g++	6_zigzag_case_3	AC	116 ms	11 MB
g++	6_zigzag_case_4	AC	101 ms	11 MB
g++	6_zigzag_case_5	AC	100 ms	11 MB
g++	6_zigzag_case_6	AC	100 ms	11 MB
g++	6_zigzag_case_7	AC	99 ms	11 MB
g++	6_zigzag_case_8	AC	100 ms	11 MB
g++	6_zigzag_case_9	AC	100 ms	11 MB
g++	7_hand_case_1	AC	2 ms	3 MB
g++	7_only_case_1	AC	88 ms	11 MB
g++	7_only_case_2	AC	89 ms	11 MB
clang++	01_sample_01	AC	2 ms	3 MB
clang++	01_sample_02	AC	2 ms	3 MB
clang++	01_sample_03	AC	2 ms	4 MB
clang++	4_small_case_1	AC	3 ms	4 MB
clang++	4_small_case_10	AC	3 ms	4 MB
clang++	4_small_case_2	AC	3 ms	4 MB
clang++	4_small_case_3	AC	3 ms	4 MB
clang++	4_small_case_4	AC	3 ms	4 MB
clang++	4_small_case_5	AC	3 ms	4 MB
clang++	4_small_case_6	AC	3 ms	4 MB
clang++	4_small_case_7	AC	3 ms	4 MB
clang++	4_small_case_8	AC	3 ms	4 MB
clang++	4_small_case_9	AC	3 ms	4 MB
clang++	5_max_case_1	AC	110 ms	11 MB
clang++	5_max_case_10	AC	110 ms	11 MB
clang++	5_max_case_2	AC	110 ms	11 MB
clang++	5_max_case_3	AC	110 ms	11 MB
clang++	5_max_case_4	AC	110 ms	11 MB
clang++	5_max_case_5	AC	110 ms	11 MB
clang++	5_max_case_6	AC	110 ms	11 MB
clang++	5_max_case_7	AC	110 ms	11 MB
clang++	5_max_case_8	AC	110 ms	11 MB
clang++	5_max_case_9	AC	113 ms	11 MB
clang++	6_zigzag_case_1	AC	104 ms	11 MB
clang++	6_zigzag_case_10	AC	105 ms	11 MB
clang++	6_zigzag_case_2	AC	106 ms	11 MB
clang++	6_zigzag_case_3	AC	106 ms	11 MB
clang++	6_zigzag_case_4	AC	106 ms	11 MB
clang++	6_zigzag_case_5	AC	106 ms	11 MB
clang++	6_zigzag_case_6	AC	105 ms	11 MB
clang++	6_zigzag_case_7	AC	104 ms	11 MB
clang++	6_zigzag_case_8	AC	106 ms	11 MB
clang++	6_zigzag_case_9	AC	105 ms	11 MB
clang++	7_hand_case_1	AC	3 ms	4 MB
clang++	7_only_case_1	AC	93 ms	11 MB
clang++	7_only_case_2	AC	94 ms	11 MB

Back to top page