#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(long long int lIndex = startLeftIndex, long long int rIndex = endRightIndex, LL v = unitValue) : leftIndex(lIndex), rightIndex(rIndex), value(v) { } Node operator + (const Node& monoid) const { return Node(startLeftIndex, endRightIndex, this->getValue() + monoid.getValue()); } static Node unit() { return Node(unitValue); } void setValue(LL l) { this->value = l; } LL getValue() const { return this->value; } pair getIndexRange() { return make_pair(leftIndex, rightIndex); } bool isLeafNode() { auto it = getIndexRange(); return it.second - it.first <= 1; } //値の設定 void setValue(long long int index, LL value) { auto indexRange = getIndexRange(); long long int leftIndex = indexRange.first, midIndex = (indexRange.first + indexRange.second)/2, rightIndex = indexRange.second; if(isLeafNode()) { if(leftIndex <= index && index < rightIndex) { setValue(value); } return; } if(!left_child) { left_child = unique_ptr(new Node(leftIndex, midIndex)); } if(!right_child) { right_child = unique_ptr(new Node(midIndex, rightIndex)); } if(leftIndex <= index && index < midIndex) { left_child->setValue(index, value); } else { right_child->setValue(index, value); } //戻るときに値を更新していく Node lNode, rNode; lNode.setValue(left_child->getValue()); rNode.setValue(right_child->getValue()); setValue((lNode + rNode).getValue()); } LL query(long long int l, long long int r) { auto indexRange = getIndexRange(); if(l <= indexRange.first && indexRange.second <= r) { return getValue(); } else if(indexRange.second <= l || r <= indexRange.first) { return Node::unit().getValue(); } else { LL ll = Node::unit().getValue(), rr = Node::unit().getValue(); if(left_child) { ll = left_child->query(l, r); } if(right_child) { rr = right_child->query(l, r); } Node lNode, rNode; lNode.setValue(ll); rNode.setValue(rr); return (lNode + rNode).getValue(); } } private: LL value; static const LL unitValue = 0; static const LL startLeftIndex = -1145141919810364, endRightIndex = 1145141919810364; unique_ptr left_child, right_child; long long int leftIndex, rightIndex; }; template class SegmentTree { public: SegmentTree() { root = unique_ptr(new Node()); } void setValue(long long int index, LL value) { root->setValue(index, value); } LL query(long long int l, long long int r) { return root->query(l, r); } private: unique_ptr root; }; #define int long long const int MAX_N = 300005; int N; class Child { public: int a, l, r; bool operator < (const Child& c) const { return a+r < c.a+c.r; } }children[MAX_N]; signed main() { unique_ptr > segmentTree = unique_ptr > (new SegmentTree()); cin >> N; for(int i = 0; i < N; i++) { cin >> children[i].a; } for(int i = 0; i < N; i++) { cin >> children[i].l >> children[i].r; } int ans = 0; set S; for(int i = 0; i < N; i++) { //cerr << i << "***" << endl; const Child& child = children[i]; //Sから出す auto it = S.begin(); while(it != S.end()) { const Child& c = *it; if(c.a + c.r < child.a) { //cerr << "erase: " << c.a << endl; segmentTree->setValue(c.a, 0); it = S.erase(it); } else { break; } } //cerr << child.a - child.l << " " << child.a + child.r + 1 << endl; ans += segmentTree->query(child.a - child.l, child.a + child.r + 1); //Sに入れる S.insert(child); segmentTree->setValue(child.a, 1); //cerr << "Segment: " << child.a << endl; } cout << ans << endl; return 0; }