結果

問題 No.3128 Isosceles Triangle
ユーザー ゼリトキ
提出日時 2025-04-25 22:12:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 439 ms / 2,500 ms
コード長 1,661 bytes
コンパイル時間 3,754 ms
コンパイル使用メモリ 286,072 KB
実行使用メモリ 16,384 KB
最終ジャッジ日時 2025-04-25 22:13:28
合計ジャッジ時間 9,483 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define mod 998244353
class MATH{
    public:
    long long factorial[500009];
    void factorial_init(int N,int m){
        long long p=1;
        for(int i=1;i<=N;i++){
            p=(p*i)%m;
            factorial[i]=p;
        }
        return;
    }
    long long power(long long a,long long b,long long m){
        long long p=a,Answer=1;
        for(long long i=0;i<60;i++){
            long long wari=(1LL<<i);
            if((b/wari)%2==1){
                Answer=(Answer*p)%m;
            }
            p=(p*p)%m;
        }
        return Answer;
    }
    long long Division(long long a,long long b,long long m){
        return (a*power(b,m-2,m))%m;
    }
    long long modinv(long long x){
        return power(x,mod-2,mod);
    }
    long long combination(long long n,long long r,long long m){
        long long bunbo=factorial[n];
        long long bunsi=(factorial[r]*factorial[n-r])%m;
        return Division(bunbo,bunsi,m);
    }
};
MATH math;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    int N;
    cin>>N;
    vector<int>A(N);
    rep(i,N) cin>>A[i];
    map<int,int>M;
    rep(i,N){
        if(M.count(A[i])) M[A[i]]++;
        else M[A[i]]=1;
    }
    sort(A.begin(),A.end());
    A.erase(unique(A.begin(),A.end()),A.end());
    ll cnt=0;
    ll r=0;
    ll ans=0;
    rep(i,A.size()){
        while(r<A.size() && A[i]*2>A[r]){
            cnt+=M[A[r]];
            r++;
        }
        cnt-=M[A[i]];
        ans+=cnt*M[A[i]]*(M[A[i]]-1)/2;
        cnt+=M[A[i]];
    }
    cout<<ans<<endl;
}
0