#include #define show(x) std::cerr << #x << " = " << x << std::endl using ll = long long; using ull = unsigned long long; constexpr std::size_t PC(const ull v) { ull count = (v & 0x5555555555555555ULL) + ((v >> 1) & 0x5555555555555555ULL); count = (count & 0x3333333333333333ULL) + ((count >> 2) & 0x3333333333333333ULL); count = (count & 0x0f0f0f0f0f0f0f0fULL) + ((count >> 4) & 0x0f0f0f0f0f0f0f0fULL); count = (count & 0x00ff00ff00ff00ffULL) + ((count >> 8) & 0x00ff00ff00ff00ffULL); count = (count & 0x0000ffff0000ffffULL) + ((count >> 16) & 0x0000ffff0000ffffULL); return static_cast((count & 0x00000000ffffffffULL) + ((count >> 32) & 0x00000000ffffffffULL)); } constexpr std::size_t LG(ull v) { return v == 0 ? 0 : (v--, v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), PC(v)); } constexpr ull SZ(const ull v) { return 1ULL << LG(v); } struct Sum { using T = ll; T operator()(const T& a, const T& b) const { return a + b; } static T inv(const T& a) { return -a; } static constexpr T id() { return 0; } }; template class BinaryIndexedTree { public: using T = typename Base::T; using AbelGroup = Base; BinaryIndexedTree(const std::size_t n) : data_num(n), size(SZ(n)), value(size + 1, Base::id()) {} T accumulate(const std::size_t a) const // [0,a] { T sum = Base::id(); for (std::size_t ind = a + 1; ind != 0; ind &= ind - 1) { sum = op(sum, value[ind]); } return sum; } T accumulate(const std::size_t l, const std::size_t r) const { return op(accumulate(r - 1), Base::inv(l == 0 ? Base::id() : accumulate(l - 1))); } void add(const std::size_t a, const T& val) { for (std::size_t ind = a + 1; ind <= size; ind += ind & (-ind)) { value[ind] = op(value[ind], val); } } private: const std::size_t data_num, size; const Base op{}; std::vector value; }; int main() { std::size_t N; std::cin >> N; std::vector A(N), R(N); using P = std::pair>; // (座標,(Aiの値か,添字)) std::vector

X; for (std::size_t i = 0; i < N; i++) { std::cin >> A[i], X.push_back({A[i], {true, i}}); } for (std::size_t i = 0, L; i < N; i++) { std::cin >> L >> R[i], X.push_back({A[i] - L, {false, i}}); } std::sort(X.begin(), X.end()); BinaryIndexedTree bit(N); ll ans = 0; for (const auto p : X) { const std::size_t i = p.second.second; if (p.second.first) { const std::size_t k = std::lower_bound(A.begin(), A.end(), p.first + R[i] + 1) - A.begin(); ans += bit.accumulate(i + 1, k); } else { bit.add(i, 1); } } std::cout << ans << std::endl; return 0; }