BOJ 15976 : XCorr

www.acmicpc.net/problem/15976

15976번: XCorr

처음에는 어려웠는데, 생각해보니 진짜 쉬운 문제였다. 

그냥 x_i를 기준으로 해서 범위 안의 y_i를 모두 더한다. 이는 Prefix-Sum을 활용하고, a_i값에 알맞게 범위를 찾아주는 것은 이분 탐색을 활용하거나 표준 라이브러리를 이용한 lower_bound, upper_bound를 이용한다.

 

#include <bits/stdc++.h>
#define MEM 300005
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll MOD = 1e9+7;
ll n,m;
ll a[MEM], ai[MEM];
ll b[MEM], bi[MEM];
ll l,r;
ll ans;
int main()
{
    sanic; cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> ai[i] >> a[i];
    cin >> m;
    for(int i=0; i<m; i++)
        cin >> bi[i] >> b[i];
    for(int i=1; i<m; i++)
        b[i] += b[i-1];
    cin >> l >> r;
    for(int i=0; i<n; i++){
        ll s=lower_bound(bi, bi+m, ai[i]+l)-bi-1;
        ll e=upper_bound(bi, bi+m, ai[i]+r)-bi-1;
        ans += a[i]*(b[e]-b[s]);
    }
    cout << ans;
}