#include #include #include using namespace std; #define INF 100000000 #define YJ 1145141919 #define INF_INT_MAX 2147483647 #define INF_LL_MAX 9223372036854775807 #define EPS 1e-10 #define MOD 1000000007 #define Pi acos(-1) #define LL long long #define ULL unsigned long long #define LD long double class Node { public: Node(LL v = unitValue) : value(v) { } Node operator + (const Node& monoid) const { return Node(this->getValue() + monoid.getValue()); } static Node unit() { return Node(unitValue); } void setValue(LL l) { this->value = l; } LL getValue() const { return this->value; } private: LL value; static const LL unitValue = 0; }; template class SegmentTree { public: SegmentTree(int size) { init(size); } void init(int size) { vec.clear(); k = 1; while(k < size) { k *= 2; } for(int i = 0; i < 2*k; i++) { vec.push_back(T::unit()); } } void update(int i, T x) { //iをxに変更する i += k-1; vec[i] = x; while(i > 0) { i = (i-1)/2; vec[i] = vec[i*2+1] + vec[i*2+2]; } } T find(int l, int r) { return _find(l, r, 0, 0, k); } private: vector vec; int k; T _find(int l, int r, int k, int x, int y) { if (r <= x || y <= l) { //重なってない場合 return T::unit(); } else if (l <= x && y <= r) { //完全にかぶってる場合 return vec[k]; } else { //中途半端にかぶってる場合 int mid = (x+y)/2; T lNode = _find(l, r, 2*k+1, x, mid); T rNode = _find(l, r, 2*k+2, mid, y); return lNode + rNode; } } }; #define int long long const int MAX_N = 300005; int N; class Child { public: int a, l, r; int index; bool operator < (const Child& c) const { return a+r < c.a+c.r; } }children[MAX_N]; int A[MAX_N]; signed main() { unique_ptr > segmentTree = unique_ptr > (new SegmentTree(MAX_N)); cin >> N; for(int i = 0; i < N; i++) { cin >> children[i].a; A[i] = children[i].a; segmentTree->update(i, 1); } for(int i = 0; i < N; i++) { cin >> children[i].l >> children[i].r; children[i].index = i; } int ans = 0; vector > vec; for(int i = 0; i < N; i++) { vec.push_back(make_pair(children[i].a + children[i].r, i+1)); vec.push_back(make_pair(children[i].a, -(i+1))); } sort(begin(vec), end(vec)); for(auto it : vec) { int index = it.second; if(index > 0) { index--; segmentTree->update(index, 0); } else { index = -1*index; index--; const Child& child = children[index]; int l = lower_bound(A, A+index, child.a - child.l) - A; ans += segmentTree->find(l, index).getValue(); } } cout << ans << endl; return 0; }