#287621 (C++17) No.728 ギブ and テイク

• 問題: No.728 ギブ and テイク
• ユーザー: たこし
• 提出日時: 2018-09-28 16:33:42
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 4,578 bytes
• コンパイル時間: 2,156 ms
• コンパイル使用メモリ: 224,168 KB
• 実行使用メモリ: 361,164 KB
• 最終ジャッジ日時: 2024-10-12 04:53:18
• 合計ジャッジ時間: 18,764 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,816 KB
testcase_01	AC	2 ms; 6,820 KB
testcase_02	AC	2 ms; 6,816 KB
testcase_03	AC	1 ms; 6,816 KB
testcase_04	AC	2 ms; 6,816 KB
testcase_05	AC	2 ms; 6,820 KB
testcase_06	AC	2 ms; 6,816 KB
testcase_07	AC	2 ms; 6,816 KB
testcase_08	AC	2 ms; 6,816 KB
testcase_09	AC	1 ms; 6,816 KB
testcase_10	AC	2 ms; 6,816 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	586 ms; 130,032 KB
testcase_23	AC	369 ms; 87,936 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	560 ms; 125,420 KB
testcase_27	WA	-
testcase_28	AC	1,266 ms; 361,164 KB
testcase_29	AC	2 ms; 6,816 KB
testcase_30	AC	2 ms; 6,816 KB
testcase_31	AC	1 ms; 6,816 KB
testcase_32	AC	1 ms; 6,816 KB

ソースコード

#include <bits/stdc++.h>
#include <cstdio>
#include <string>

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<LL, LL> 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<Node>(new Node(leftIndex, midIndex));
        }
        if(!right_child) {
            right_child = unique_ptr<Node>(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<Node> left_child, right_child;
    long long int leftIndex, rightIndex;
};

template <class T>
class SegmentTree {
public:
    SegmentTree() {
        root = unique_ptr<Node>(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<T> 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<Node> > segmentTree = unique_ptr<SegmentTree<Node> > (new SegmentTree<Node>());
  
  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<Child> 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;
}