Submission #20215733

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main(){
    int64_t B, C;
    cin >> B >> C;
    
    // 作れる値の区間たち（閉区間）
    vector<pair<int64_t, int64_t>> PS;

    // 先頭で-1倍しない、末尾で-1倍しない
    {
        int64_t start = B, step = C/2;
        PS.emplace_back(start-step, start);
    }
    // 先頭で-1倍しない、末尾で-1倍する
    {
        int64_t start = B, step = (C-1)/2;
        PS.emplace_back(-start, -(start-step));
    }
    // 先頭で-1倍する、末尾で-1倍しない
    {
        int64_t start = -B, step = (C-1)/2;
        PS.emplace_back(start-step, start);
    }
    // 先頭で-1倍する、末尾で-1倍する
    if(C >= 2){
        int64_t start = -B, step = (C-2)/2;
        PS.emplace_back(-start, -(start-step));
    }

    // 半開区間に直して座圧+imos法。mapを使って実装
    map<int64_t, int64_t> mp;
    for(auto [s, t] : PS){
        mp[s]++;
        mp[t+1]--;
    }
    // 座圧した点を小さいほうから見ていって、sumが正である区間の長さを合計する
    int64_t ans = 0, sum = 0, prv = -8e18;
    for(auto [pt, val] : mp){
        if(sum) ans += pt-prv;
        prv = pt;
        sum += val;
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result