結果
問題 | No.728 ギブ and テイク |
ユーザー | たこし |
提出日時 | 2018-09-28 17:12:39 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 604 ms / 3,000 ms |
コード長 | 3,070 bytes |
コンパイル時間 | 2,537 ms |
コンパイル使用メモリ | 208,488 KB |
実行使用メモリ | 40,288 KB |
最終ジャッジ日時 | 2024-04-20 09:57:43 |
合計ジャッジ時間 | 8,546 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 11 ms
13,648 KB |
testcase_01 | AC | 11 ms
13,640 KB |
testcase_02 | AC | 11 ms
13,640 KB |
testcase_03 | AC | 11 ms
13,644 KB |
testcase_04 | AC | 11 ms
13,772 KB |
testcase_05 | AC | 10 ms
13,644 KB |
testcase_06 | AC | 12 ms
13,772 KB |
testcase_07 | AC | 11 ms
13,644 KB |
testcase_08 | AC | 11 ms
13,772 KB |
testcase_09 | AC | 11 ms
13,772 KB |
testcase_10 | AC | 11 ms
13,776 KB |
testcase_11 | AC | 12 ms
13,644 KB |
testcase_12 | AC | 12 ms
13,772 KB |
testcase_13 | AC | 38 ms
15,180 KB |
testcase_14 | AC | 55 ms
17,744 KB |
testcase_15 | AC | 29 ms
14,540 KB |
testcase_16 | AC | 49 ms
15,440 KB |
testcase_17 | AC | 46 ms
15,440 KB |
testcase_18 | AC | 422 ms
34,700 KB |
testcase_19 | AC | 448 ms
35,236 KB |
testcase_20 | AC | 531 ms
39,920 KB |
testcase_21 | AC | 475 ms
35,000 KB |
testcase_22 | AC | 186 ms
23,352 KB |
testcase_23 | AC | 124 ms
19,904 KB |
testcase_24 | AC | 347 ms
32,140 KB |
testcase_25 | AC | 349 ms
33,616 KB |
testcase_26 | AC | 180 ms
23,196 KB |
testcase_27 | AC | 604 ms
40,028 KB |
testcase_28 | AC | 507 ms
40,288 KB |
testcase_29 | AC | 11 ms
13,772 KB |
testcase_30 | AC | 12 ms
13,640 KB |
testcase_31 | AC | 12 ms
13,768 KB |
testcase_32 | AC | 12 ms
13,772 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(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 T> 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<T> 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<Node> > segmentTree = unique_ptr<SegmentTree<Node> > (new SegmentTree<Node>(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<pair<int, int> > 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; }