Submission #63313

#	Time	Username	Problem	Language	Result	Execution time	Memory
63313		kjp4155	XCorr (KOI18_XCorr)	C++17	100 / 100	292 ms	30816 KiB

XCorr

#include <stdio.h>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;

const ll inf = 1e18;

int N,M;
int a,b;
// 수열 X,Y의 (index, value) 쌍을 저장한다. S에는 Y의 누적합 배열을 저장한다
vector<pair<ll,ll>> X,Y,S;

int main(){
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		ll idx, val; scanf("%lld%lld",&idx,&val);
		X.push_back(make_pair(idx,val));
	}

	scanf("%d",&M);
	for(int i=0;i<M;i++){
		ll idx, val; scanf("%lld%lld",&idx,&val);
		Y.push_back(make_pair(idx,val));
	}

	scanf("%d%d",&a,&b);

	// Y의 누적합 배열 S를 계산한다
	S.resize(M);
	for(int i=0;i<M;i++){
		S[i] = Y[i];
		if( i > 0 ) S[i].second += S[i-1].second;
	}

	ll ans = 0;
	for(int i=0;i<N;i++){
		ll idx = X[i].first, val = X[i].second;

		// X[i]와 관련있는 Y값들의 합을 sum에 저장하자
		ll sum = 0;

		// idx+b 에 해당하는 누적합 배열의 우측 값을 구하자.
		// 이분탐색 결과로 나온 iterator가 S.begin()인 경우를 유의한다. (it1-- 에서 런타임 에러 발생 가능)
		// idx+b 가 음수라 [idx+a, idx+b]에 해당하는 y값들이 모두 0인 경우 넘어간다
		auto it1 = upper_bound(S.begin(), S.end(), make_pair(idx+b, inf));
		if( it1 == S.begin() ) continue;
		it1--;

		sum += (*it1).second;

		// idx+a-1 에 해당하는 누적합 배열의 좌측 값을 구하자
		// 이분탐색 결과로 나온 iterator가 S.begin()인 경우를 유의한다. (it2-- 에서 런타임 에러 발생 가능)
		auto it2 = lower_bound(S.begin(), S.end(), make_pair(idx+a, -inf));
		if( it2 != S.begin() ) {
			it2--;
			sum -= (*it2).second;
		}

		// 답에 X[i] * (관련있는 모든 Y값의 합) 를 더해 준다
		ans += sum * val;
	}

	printf("%lld\n",ans);

}

Compilation message (stderr)

XCorr.cpp: In function 'int main()':
XCorr.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
XCorr.cpp:19:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll idx, val; scanf("%lld%lld",&idx,&val);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~
XCorr.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&M);
  ~~~~~^~~~~~~~~
XCorr.cpp:25:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll idx, val; scanf("%lld%lld",&idx,&val);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~
XCorr.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&a,&b);
  ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 42 / 42
• Subtask 3: 39 / 39