Submission #402909

#	Time	Username	Problem	Language	Result	Execution time	Memory
402909		jk410	XCorr (KOI18_XCorr)	C++17	100 / 100	146 ms	7364 KiB

XCorr

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N,M,a,b,l=1,r;
int xi[300001],yi[300001];
ll x[300001],y[300001];
ll Ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    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];
        y[i]+=y[i-1];
    }
    cin>>a>>b;
    for (int i=1; i<=N; i++){
        while (l<=M&&yi[l]<xi[i]+a)
            l++;
        while (r<M&&yi[r+1]<=xi[i]+b)
            r++;
        Ans+=x[i]*(y[r]-y[l-1]);
    }
    cout<<Ans;
    return 0;
}

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