1538-C, *1300

Problem - 1538C - Codeforces

문제

• 크기가 $n(1\leq n \leq 2 \cdot 10^{5})$인 수열 $a_{1}a_{2}...a_{n-1}a_{n}$이 주어진다
• $l\leq a_{i}+a_{j} \leq r$인 $i,\ j(i \neq j)$의 개수를 구하라

 

$O(nlog\ n)$

먼저 준 수열을 sort 한다 $O(nlog\ n)$

이제 모든 원소 각각을 뽑았을 때, 조건을 만족하는 원소의 왼쪽 index와 오른쪽 index를 구해서 개수를 구한다

예를 들어 $[l,\ r] = [5,\ 8]$, 수열을 $[1,\ 2,\ 3,\ 4,\ 5]$ 라고 하자.
( ) 은 조건을 만족하는 수들이고 | 은 수를 뽑을 때 칸막이 오른쪽 수들만을 고려한다는 의미이다($\because$조합)
i) 1을 무조건 뽑음
$[1,|\ 2,\ 3,\ (4,\ 5)]$
ii) 2를 무조건 뽑음
$[1,\ 2,|\ (3,\ 4,\ 5)]$
iii) 3을 무조건 뽑음
$[1,\ 2,\ 3,|\ (4,\ 5)]$
iv) 4를 무조건 뽑음
$[1,\ 2,\ 3,\ 4,|\ 5()]$
v) 5를 무조건 뽑음
$[1,\ 2,\ 3,\ 4,\ 5()|]$

수들은 sort 되어있으므로 binary search 를 이용하여 왼쪽 index 와 오른쪽 index 를 구한다 $O(nlog\ n)$

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int n, l, r;
int pl, pr;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> n >> l >> r;
        vector<int> v(n);
        for(auto& e: v) cin >> e;
        sort(v.begin(), v.end());
 
        long long res = 0;
        for(int i = 0; i < n; i++){
            pl = lower_bound(v.begin()+i+1, v.end(), l-v[i])-v.begin();
            pr = upper_bound(v.begin()+i+1, v.end(), r-v[i])-v.begin();
            res += pr-pl;
        }
        cout << res << endl;
    }
 
    return 0;
}cs