← Real problems

ceoi19pp1

easycountinghashingStatement on DMOJ

CP Lang

7 lineschecks
// ceoi19pp1: count pairs (i < j in a, k < l in b) with a[j] - a[i] = b[l] - b[k]: tally the
// differences of a, then look up every difference of b.
let (n, m) = read<(1..=2_000, 1..=2_000)>()
let a = read<[n]Int>()
let b = read<[m]Int>()
let seen = a.pairs().map(p => p.1 - p.0).tally()
print(b.pairs().map(p => seen.get(p.1 - p.0) ?? 0).sum())

Accepted C++

62 lines · 7.15 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

void solve() {
    int n, m;
    cin >> n >> m;
    int arra[n], arrb[m];
    for (auto& a : arra) {
        cin >> a;
    }
    for (auto& a : arrb) {
        cin >> a;
    }
    map<int, int> cnt;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            cnt[arra[j] - arra[i]]++;
        }
    }
    long ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            ans += cnt[arrb[j] - arrb[i]];
        }
    }
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}