Submission #65661

#	Time	Username	Problem	Language	Result	Execution time	Memory
65661		imeimi2000	XCorr (KOI18_XCorr)	C++17	100 / 100	217 ms	12368 KiB

XCorr

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n, m;
int seg[1 << 20];
pii xs[300000];
pii ys[300000];
void init(int i, int s, int e) {
    if (s == e) {
        seg[i] = xs[s].second;
        return;
    }
    int m = (s + e) / 2;
    init(i << 1, s, m);
    init(i << 1 | 1, m + 1, e);
    seg[i] = seg[i << 1] + seg[i << 1 | 1];
}

int query(int i, int s, int e, int x, int y) {
    if (xs[e].first < x || y < xs[s].first) return 0;
    if (x <= xs[s].first && xs[e].first <= y) return seg[i];
    int m = (s + e) / 2;
    return query(i << 1, s, m, x, y) + query(i << 1 | 1, m + 1, e, x, y);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
        cin >> xs[i].first >> xs[i].second;
	}
	init(1, 0, n - 1);
	cin >> m;
	for (int i = 0; i < m; ++i) {
        cin >> ys[i].first >> ys[i].second;
	}
	int a, b;
	cin >> a >> b;
	llong ans = 0;
	for (int i = 0; i < m; ++i) {
        ans += (llong)ys[i].second
         * query(1, 0, n - 1, ys[i].first - b, ys[i].first - a);
	}
	printf("%lld\n", ans);
	return 0;
}

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