백준15976 XCorr

작성일 | In

문제 링크

  • http://icpc.me/15976

문제 출처

  • 2018 KOI 전국 본선 고등부2

사용 알고리즘

  • parametric search

시간복잡도

  • O(n log m)

풀이

고등 2번에 맞지 않는 너무 쉬운 문제라고 생각합니다.

예제 몇 개를 만들어 그림을 그려보면 각각의 xi에 곱해지는 yj는 연속적인 것을 알 수 있습니다.
y에 있는 0이 아닌 m개의 수열의 값을 누적합으로 저장하고, 인덱스들을 따로 저장을 해줍시다.
저장된 인덱스와 누적합을 활용해 parametric search를 돌리면 각각의 xi에 곱해지는 yj의 범위와 값을 쉽게 알 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
vector<ll> arr, aidx, bidx, sum;
int n, m;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	arr.resize(n), aidx.resize(n);
	for(int i=0; i<n; i++){
		ll idx, value; cin >> idx >> value;
		arr[i] = value;
		aidx[i] = idx;
	}
	cin >> m;
	bidx.resize(m+10), sum.resize(m+10);
	for(int i=0; i<m; i++){
		ll idx, value; cin >> idx >> value;
		bidx[i] = idx;
		sum[i+1] = sum[i] + value;
	}
	for(int i=m; i<m+10; i++) bidx[i] = 1e18;
	int a, b; cin >> a >> b;

	ll ans = 0;
	for(int i=0; i<n; i++){
		int low = lower_bound(bidx.begin(), bidx.end(), aidx[i]+a) - bidx.begin();
		int high = lower_bound(bidx.begin(), bidx.end(), aidx[i]+b+1) - bidx.begin();
		ll go = arr[i] * (sum[high] - sum[low]);
		ans += go;
	}
	cout << ans;
}