Submission #108182

#	Time	Username	Problem	Language	Result	Execution time	Memory
108182		aer0park	XCorr (KOI18_XCorr)	C++14	100 / 100	205 ms	18008 KiB

XCorr

#include <bits/stdc++.h>
#define f first
#define s second
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pi;
 
ll n,m,mx,mn,anw;
vector<pi> px,y;
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	px.push_back({-1e10,0});
	for(int i=0;i<n;i++)
	{
		ll a,b;cin>>a>>b;	
		px.push_back({a,px[i].s+b});
	}	
	cin>>m;
	for(int i=0;i<m;i++)
	{
		ll a,b;cin>>a>>b;
		y.push_back({a,b});
	}	
	cin>>mn>>mx;
	mn=-mn,mx=-mx;
	swap(mn,mx);
	for(int i=0;i<m;i++)
	{
		ll nw=y[i].f,nv=y[i].s,a=1,b=0;
		if(nw+mx<0)
			continue;
		b=upper_bound(px.begin(),px.end(),pi(nw+mx,1e11))-px.begin();
		if(nw+mn>=0)
			a=lower_bound(px.begin(),px.end(),pi(nw+mn,-1e11))-px.begin();
		anw+=nv*(px[b-1].s-px[a-1].s);
	}
	cout<<anw;
	return 0;
}

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