計算量が同じはずなのに定数倍とは思えないほどの計算量の差が出ます

Question

#発生している問題
第6回情報オリンピック本選の過去問第三番を解いている際に発生しました。この問題は概して言うとx-y平面内にあるn(<=3000)個の点の座標が与えられ、それらのうち4点がなす正方形の面積の最大値を求めよと言うものです。着想した解法は想定解と同じで、n個の点のうち異なる2個の組み合わせ全通りに対して、そこから時計回りおよび反時計回りに正方形をなすような残りの2点が存在するかを判定していく、ということを思いつきました(計算量はO(n^2logn)となり間に合うはずです)。しかし、実装の段階になって問題が生じました。
前述の「時計回りおよび反時計回りに正方形をなすような残りの2点が存在するか」を判定する際に、予めn個の座標をpair<long long (x座標), long long (y座標)>をkeyとするmapとして格納しておきました。そして書いたコードが以下(関係ないdefine等は削ってあります。元のコードはこちら)です。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>
#include <iomanip>
#include <unordered_map>
#include <map>
#include <boost/multiprecision/cpp_int.hpp>
 
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;

 
int main(void){
    ll n;
    cin>>n;
    vector<pair<ll, ll> > cols;
    map<pair<ll, ll> , ll> ma;
    rep(i,n){
        ll x, y;
        cin>>x>>y;
        cols.push_back({x, y});
        ma[{x, y}]++;
    }
    ll Maxima=0;
    rep(i, n-1) reps(j, i+1, n){
        ll dx=cols[j].first-cols[i].first;
        ll dy=cols[j].second-cols[i].second;

　　　　　//以下mapによる判定処理
        if(ma[{cols[i].first-dy, cols[i].second+dx}]!=0 && ma[{cols[j].first-dy, cols[j].second+dx}]!=0){
            Maxima=max(Maxima, dx*dx+dy*dy);
        }
        if(ma[{cols[i].first+dy, cols[i].second-dx}]!=0 && ma[{cols[j].first+dy, cols[j].second-dx}]!=0){
            Maxima=max(Maxima, dx*dx+dy*dy);
        }

    }
    cout<<Maxima<<endl;
    return 0;
}

こちらのコードは実行時間3314 ms、メモリ使用量235980 KBになりました。計算量解析と反し、これらはどちらも問題の制限を超えており、不正解になります。
一方、他の方提出したコードを参考に、上記のコードの「mapによる判定処理」にあたる部分で、mapの要素に直接アクセスするのではなく、map.count()によって要素が存在するかを判定したコードに直してみました。それが以下(これも関係ないdefine等は削ってあります。元のコードはこちら)になります。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>
#include <iomanip>
#include <unordered_map>
#include <map>
#include <boost/multiprecision/cpp_int.hpp>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;

int main(void){
    ll n;
    cin>>n;
    vector<pair<ll, ll> > cols;
    map<pair<ll, ll> , ll> ma;
    rep(i,n){
        ll x, y;
        cin>>x>>y;
        cols.push_back({x, y});
        ma[{x, y}]++;
    }
    ll Maxima=0;
    rep(i, n-1) reps(j, i+1, n){
        ll dx=cols[j].first-cols[i].first;
        ll dy=cols[j].second-cols[i].second;

        //以下はmapによる判定処理(修正版)
        if(ma.count({cols[i].first-dy, cols[i].second+dx}) && ma.count({cols[j].first-dy, cols[j].second+dx})){
            Maxima=max(Maxima, dx*dx+dy*dy);
        }
        if(ma.count({cols[i].first+dy, cols[i].second-dx}) && ma.count({cols[j].first+dy, cols[j].second-dx})){
            Maxima=max(Maxima, dx*dx+dy*dy);
        }

    }
    cout<<Maxima<<endl;
    return 0;
}

要するに、ma[座標]!=0によって判定していたものを、ma.count(座標)に書き換えただけです。これらはどちらもC++のレファレンスによるとO(log n)で計算できるはずで、計算時間に大きな改善が見られるとは思えません。しかし、こちらのコードは、全く同一のテストケースに実行時間619 ms、メモリ3868 KBと大幅に改善しました。これは十分に正解になる値です。ただアクセスの仕方を変えただけなのに、メモリ使用量が桁が二つ違うのは異常に思えます。

この計算量の差は一体どこから生じるのでしょうか？詳しい方、ご教授いただけるとありがたいです。よろしくお願い申し上げます。

#環境
Atcoderのオンラインジャッジシステムで、コンパイラはC++ (GCC 9.2.1)です。

※追記　解決しました。3方ともご回答ありがとうございました。ベストアンサーを選ばなければ解決済みにならないようなので、どれも同様に解決に役立ちましたが、最も回答の早かったものをベストアンサーにさせていただきます。

Answer 1

mapのoperator[]は，要素が無い場合に追加します．
そこで差が出るのではないでしょうか．

Comments

[InfoFault]

そういうことなんですね！わかりました。ご回答ありがとうございます！

Answer 2

map 型の ma があるとき ma[座標] として要素にアクセスを試みてその要素が存在しなければ「自動的にその要素をデフォルト生成」します。 有るか無いか調べたいだけなのに常に要素は有ることになってしまうのです。

不必要に要素が生成されてしまう分だけメモリ・時間のコストが増大してしまいます。

Comments

[InfoFault]

なるほど、その仕様によって要素数が増加していってしまうのですね！腑に落ちました。ご回答ありがとうございました。

Answer 3

map::operator[]は、キーに対応する値が存在しない場合、デフォルト構築した値をマップに挿入するようになっています（cpprefjp）。

単にチェックするだけの動作ではなく、意味もなくmapを肥大化させるコードになってしまっています。

Comments

[InfoFault]

そこの仕様を完全に見落としていました…
解決しました！ご回答ありがとうございます！