結果
問題 |
No.1110 好きな歌
|
ユーザー |
![]() |
提出日時 | 2020-07-17 19:41:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 660 ms / 5,000 ms |
コード長 | 1,423 bytes |
コンパイル時間 | 1,767 ms |
コンパイル使用メモリ | 177,368 KB |
実行使用メモリ | 42,496 KB |
最終ジャッジ日時 | 2024-11-29 14:58:40 |
合計ジャッジ時間 | 18,498 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n, d; scanf("%lld%lld", &n, &d); if (n < 2) { printf("0\n"); return 0; } map<ll, ll> m; vector<ll> a(n); for (int i = 0; i < n; ++i) { ll ai; scanf("%lld", &ai); a[i] = ai; ++m[ai]; } map<ll, ll> mconv; for (const auto& im : m) { if (im.first <= d) { mconv[im.first] = 0; continue; } auto iml = m.upper_bound(im.first - d); if (iml != m.begin()) mconv[im.first] = (--iml)->first; } map<ll, ll> mc; ll prev{ m.begin()->first }; for (const auto& im : m) { mc[im.first] = 0; if (im.first == m.begin()->first) continue; else if (im.first <= d) { prev = im.first; continue; } mc[im.first] = mc[prev]; auto iml = m.upper_bound(mconv[prev]); auto imr = m.upper_bound(mconv[im.first]); for (auto imt = iml; imt != imr; ++imt) { mc[im.first] += imt->second; } prev = im.first; } ll res; for (int i = 0; i < n; ++i) { res = mc[a[i]]; printf("%lld\n", res); } return 0; }