結果

問題 No.33 アメーバがたくさん
コンテスト
ユーザー Konton7
提出日時 2020-02-05 01:25:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,763 bytes
コンパイル時間 2,536 ms
コンパイル使用メモリ 210,096 KB
最終ジャッジ日時 2025-01-08 22:09:17
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)


PLL divide(ll m, int t)
{
    PLL ret;
    ret.first = m - t;
    ret.second = m + t;
    return ret;
}

int main()
{

#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif

    int n, d, t, c;
    ll x, l, r, ans;
    map<int, int> mod;
    vector<ll> ameba;
    cin >> n >> d >> t;
    c = 0;
    rep(i, n)
    {
        cin >> x;
        ameba.push_back(x);
        if (mod[((x % d) + d) % d] == 0)
        {
            c++;
            mod[((x % d) + d) % d] = c;
        }
    }
    // cout << mod.size() << endl;

    vector<ll> ameba2[c];
    vector<pair<ll, ll>> ameba3[c];
    sort(ameba.begin(), ameba.end());

    for (auto z : ameba)
    {
        if (z >= 0)
            ameba2[mod[((z % d) + d) % d] - 1].push_back(z / d);
        else
            ameba2[mod[((z % d) + d) % d] - 1].push_back((z - d + 1) / d);
    }

    rep(i, c)
    {
        for (auto z : ameba2[i])
        {
            ameba3[i].push_back(divide(z, t));
        }
    }

    ans = 0;
    for (auto y : ameba3)
    {
        for (auto i = 0; i < y.size(); i++)
        {
            // cout << y[i].first << " " << y[i].second << "\t";
            if (i == 0)
                l = y[i].first, r = y[i].second;
            else
            {
                l = max(r + 1, y[i].first);
                r = y[i].second;
            }

            ans += r - l + 1;
        }
        // cout << endl;
    }
    cout << ans << endl;
    return 0;
}
0