Help us understand the problem. What is going on with this article?

AtCoder Beginner Contest 084 C - Snuke Festival

C - Snuke Festival

各段が10^5あってあれ2重ループでも間に合わない...
となってしまった。

2段目を基準としてlower_bound, upper_boundを使ってA, Cの値を求めて足し合わせればO(N)で答えが出せる。

lower_bound: 指定したvalue 以上 の最初の要素の位置をイテレータで返す
upper_bound: 指定したvalue より大きい 最初の要素の位置をイテレータで返す
イテレータで返すのでそこも注意ですね。

これらを用いて実装をしていきました。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;
const ll C = 1e9+7;

int main() {
    int N;
    cin >> N;
    vector<int> A(N), B(N), C(N);
    for(int i=0; i<N; i++) cin >> A[i];
    for(int i=0; i<N; i++) cin >> B[i];
    for(int i=0; i<N; i++) cin >> C[i];

    sort(A.begin(), A.end());
    sort(C.begin(), C.end());

    ll ans = 0;

    for(int i=0; i<N; i++) {
        //lower_bound: 指定したvalue以上の最初の要素の位置をイテレータで返す
        ll pre = lower_bound(A.begin(), A.end(), B[i]) - A.begin();

        //upper_bound: 指定したvalueより大きい最初の要素の位置をイテレータで返す
        ll over = C.end() - upper_bound(C.begin(), C.end(), B[i]);

        ans += pre * over;
    }
    cout << ans << endl;
}
akilax
営業社員からエンジニアになりました。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away