(BOJ) 15976 XCorr (테스트 케이스)

문제: https://www.acmicpc.net/problem/15976

 

문제 풀이:

이걸 x에 대해 묶으면

-> X0(Y-1+Y0+Y1) + x1(Y0+Y1+Y2)+X2(Y1+Y2+Y3) ..... `

즉, a≤t≤b라고 할 때

Xi*{ Y(i+a)~Y(i+b)} + .... 가 된다.

여기서 Y(i+a)~Y(i+b)는 미리 합을 저장해 둔 후 구간 합을 구한다.

 

y의 인덱스를 저장하는 벡터를 따로 만들어서 lower bound를 통해 구간을 찾는다

만약 y가 다음과 같을 때,

i	0	1	2	3	4
Yi			7	5	2

y의 인덱스를 저장하는 벡터에는 다음과 같이 저장된다. -> 2,3,4

0~1 구간을 찾게 되면, P1=0, p2=0이 되고, (y의 인덱스 저장하는 벡터)[0]은 2인데 1보다 크므로 p2--가 되서

p1>p2가 된다. 이 때는 해당 t값에서 Xi에 대해 값을 가지는 y값이 없는 것이므로 연산하지 말고 continue 해줘야 한다.

 

 

 

소스 코드:

typedef long long ll;
vector<ll> pos2, b;
vector<pair<ll, ll>> a;
int n, m;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n;
	ll q, w;
	for (int i = 0; i < n; i++) {
		cin >> q >> w;
		a.push_back({ q,w });
	}
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> q >> w;
		pos2.push_back(q);
		if (i == 0) b.push_back(w);
		else b.push_back(w + b[i - 1]);
	}
	cin >> q >> w;
	ll res = 0;
	ll len = a.size();
	for (int i = 0; i < len; i++) {
		ll idx = a[i].first;
		ll p1 = lower_bound(pos2.begin(), pos2.end(), idx + q) - pos2.begin();
		ll p2 = lower_bound(pos2.begin(), pos2.end(), idx + w) - pos2.begin();
		if (p2 == pos2.size() || pos2[p2] > idx + w) p2--;
		if (p2 < p1) continue;
		if (p1 == 0) res += a[i].second * b[p2];
		else res += a[i].second * (b[p2] - b[p1 - 1]);
	}
	cout << res << '\n';
	return 0;
}

 

테스트 케이스:

case1)

1 
1 5 
1 
2 2 
-1 1 
-> 10 

 

case2)
4 
0 1 
1 2 
2 3 
3 4 
3 
1 5 
2 7 
4 2 
-1 1 
->101 

 

case3)
4 
0 1 
1 2 
2 3 
3 4 
3 
2 7 
3 5 
4 2 
-1 1 
-> 106