Submission #152139

#	Time	Username	Problem	Language	Result	Execution time	Memory
152139		gs18103	XCorr (KOI18_XCorr)	C++14	100 / 100	185 ms	20812 KiB

XCorr

#include <bits/stdc++.h>

using namespace std;

long long X[303030], Y[303030], Xi[303030], Yi[303030], SY[303030];

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int n, m, a, b;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> Xi[i] >> X[i];
	}
	cin >> m;
	for(int i = 1; i <= m; i++) {
		cin >> Yi[i] >> Y[i];
	}
	cin >> a >> b;

	for(int i = 1; i <= m; i++) {
		SY[i] = SY[i-1] + Y[i];
	}

	long long ans = 0;
	for(int i = 1; i <= n; i++) {
		int l, r;
		r = upper_bound(Yi+1, Yi+m+1, Xi[i]+b)-Yi-1;
		l = lower_bound(Yi+1, Yi+m+1, Xi[i]+a)-Yi-1;
		ans += X[i] * (SY[r]-SY[l]);
	}
	cout << ans;
}

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