Submission #269545

#	Time	Username	Problem	Language	Result	Execution time	Memory
269545		sean9892	XCorr (KOI18_XCorr)	C++14	100 / 100	208 ms	21728 KiB

XCorr

#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;

const int inf=2e9;
vector<pii> x,y;
vector<int> p;
ll sum[300010];

int main(void){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,m;
	cin>>n;
	for(int i=0;i<n;i++){
		int a,b;
		cin>>a>>b;
		x.emplace_back(a,b);
	}
	cin>>m;
	p.push_back(-inf);
	sum[0]=0;
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		y.emplace_back(a,b);
		p.push_back(a);
		sum[i+1]=b;
		sum[i+1]+=sum[i];
	}
	sum[m+1]=sum[m];
	p.push_back(inf);
	int a,b;
	cin>>a>>b;
	ll res=0;
	for(int i=0;i<n;i++){
		int k=x[i].first,r=x[i].second;
		int ub,s,e;
		ub=upper_bound(p.begin(),p.end(),k+a-1)-p.begin();
		s=sum[ub-1];
		ub=upper_bound(p.begin(),p.end(),k+b)-p.begin();
		e=sum[ub-1];
		res+=1ll*r*(e-s);
	}
	cout<<res;
}

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