結果

問題 No.3128 Isosceles Triangle
ユーザー ケネン
提出日時 2025-04-25 23:09:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 654 ms / 2,500 ms
コード長 891 bytes
コンパイル時間 2,582 ms
コンパイル使用メモリ 210,908 KB
実行使用メモリ 38,332 KB
最終ジャッジ日時 2025-04-25 23:09:40
合計ジャッジ時間 10,029 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using pll = pair<ll, ll>;

set<ll> s, thr;
map<ll, ll> m;
vector<ll> v, cnt;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    v.push_back(x);
    s.insert(x);
    m[x]++;
  }
  vector<ll> p(s.begin(), s.end());
  cnt = vector<ll>(s.size()+1);

  ll sum = 0;
  for (int i = 0; i < v.size(); i++) {
    int vidx = lower_bound(p.begin(), p.end(), v[i]) - p.begin();
    int idx = upper_bound(p.begin(), p.end(), v[i]/2) - p.begin();
    if (idx <= vidx) cnt[idx]++, cnt[vidx]--, cnt[vidx+1]++;
    else cnt[idx]++;
  }

  for (int i = 0; i < cnt.size()-1; i++) {
    // cout << cnt[i] << " ";
    if (i) cnt[i] += cnt[i-1];
    ll w = p[i];
    sum += m[w]*(m[w]-1)/2*cnt[i];
  }
  cout << sum;
}
0