Submission #1244452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244452		quannnguyen2009	XCorr (KOI18_XCorr)	C++20	100 / 100	84 ms	17452 KiB

XCorr

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 3e5+5, mod = 1e9+7, inf = 1e18;

int n, m;
vector<ii> v1, v2;
int a, b;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    v1.pb({0, 0}); v2.pb({0, 0});
    cin >> n;
    for (int i=1; i<=n; i++) {
        int id, v; cin >> id >> v; id++;
        v1.pb({id, v});
    }
    cin >> m;
    for (int i=1; i<=m; i++) {
        int id, v; cin >> id >> v; id++;
        v2.pb({id, v});
    }
    cin >> a >> b;
    for (int i=1; i<sz(v2); i++) v2[i].se += v2[i-1].se;
    int ans = 0;
    for (int i=1; i<sz(v1); i++) {
        int id = v1[i].fi, v = v1[i].se;
        int lft = max(id+a, v2[1].fi), rgt = min(id+b, v2.back().fi);
        if (lft>rgt) continue;
        int l = lower_bound(all(v2), make_pair(lft, -inf))-v2.begin(), r = upper_bound(all(v2), make_pair(rgt, inf))-v2.begin()-1;
        if (l>r) continue;
        ans += (v2[r].se-v2[l-1].se)*v;
    }
    cout << ans;
}

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