結果
問題 | No.789 範囲の合計 |
ユーザー | yuppe19 😺 |
提出日時 | 2019-03-07 12:14:19 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 462 ms / 1,000 ms |
コード長 | 6,100 bytes |
コンパイル時間 | 1,118 ms |
コンパイル使用メモリ | 91,420 KB |
実行使用メモリ | 13,844 KB |
最終ジャッジ日時 | 2024-06-23 14:48:10 |
合計ジャッジ時間 | 5,056 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,940 KB |
testcase_02 | AC | 393 ms
13,236 KB |
testcase_03 | AC | 61 ms
6,940 KB |
testcase_04 | AC | 368 ms
13,072 KB |
testcase_05 | AC | 334 ms
13,460 KB |
testcase_06 | AC | 337 ms
13,312 KB |
testcase_07 | AC | 43 ms
6,944 KB |
testcase_08 | AC | 182 ms
8,736 KB |
testcase_09 | AC | 164 ms
7,588 KB |
testcase_10 | AC | 462 ms
13,844 KB |
testcase_11 | AC | 338 ms
13,140 KB |
testcase_12 | AC | 340 ms
13,144 KB |
testcase_13 | AC | 1 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,944 KB |
ソースコード
#include <iostream> #include <tuple> #include <vector> using namespace std; using i64 = int64_t; using u32 = uint32_t; void debug(const vector<int> &v) { for(size_t i=0, n=v.size(); i<n; ++i) { if(i) { fprintf(stderr, " "); } fprintf(stderr, "%d", v[i]); } fprintf(stderr, "\n"); } u32 uy = u32(time(NULL)); u32 xorshift32() { uy ^= uy << 14; uy ^= uy >> 13; uy ^= uy << 15; return uy; } template <typename T> bool __attribute__((noinline)) is_null(T* obj) { return obj == nullptr; } // RBST (Randomised Binary Search Tree) template <class T> struct RBST { struct Node { // {{{ Node constexpr static T nullval = -1; // valueAt() で不正な場所が指定されたときに返す値. T val; int treeSize; Node *lo, *hi; explicit Node(T _val) : val(_val), treeSize(1), lo(nullptr), hi(nullptr) {} int size() { if(is_null(this)) { return 0; } return treeSize; } Node* update() { treeSize = lo->size() + hi->size() + 1; return this; } static Node* merge(Node *l, Node *r) { if(is_null(l)) { return r; } if(is_null(r)) { return l; } size_t lSize = l->size(), rSize = r->size(); if(xorshift32() % (lSize + rSize) < lSize) { l->hi = merge(l->hi, r); return l->update(); } else { r->lo = merge(l, r->lo); return r->update(); } } pair<Node*, Node*> split(int k) { // [0, k), [k, n) if(is_null(this)) { return make_pair(nullptr, nullptr); } if(k <= lo->size()) { auto s = lo->split(k); lo = s.second; return make_pair(s.first, update()); } else { auto s = hi->split(k - lo->size() - 1); hi = s.first; return make_pair(update(), s.second); } } int indexOf(T x) { if(is_null(this)) { return -1; } if(x == this->val) { return lo->size(); } if(x < this->val) { return lo->indexOf(x); } else { return lo->size() + 1 + hi->indexOf(x); } } T valueAt(int pos) { if(is_null(this)) { return nullval; } int loSize = lo->size(); if(loSize == pos) { return val; } if(loSize > pos) { return lo->valueAt(pos); } else { return hi->valueAt(pos - lo->size() - 1); } } int lowerBound(T x) { if(is_null(this)) { return 0; } if(x <= this->val) { return lo->lowerBound(x); } return hi->lowerBound(x) + lo->size() + 1; } int upperBound(T x) { if(is_null(this)) { return 0; } if(x >= this->val) { return lo->size() + 1 + hi->upperBound(x); } return lo->upperBound(x); } int count(T x) { return upperBound(x) - lowerBound(x); } Node* insert(int pos, T x) { Node *p = new Node(x); auto s = split(pos); return merge(merge(s.first, p), s.second); } Node* insert(T x) { return insert(lowerBound(x), x); } Node* deleteAt(int pos) { auto s = split(pos); auto t = s.second->split(1); t.first = nullptr; return merge(s.first, t.second); } void dump(int x) { if(is_null(this)) { return; } fprintf(stderr, "%c", "([{"[x%3]); lo->dump(x+1); fprintf(stderr, "%d", this->val); hi->dump(x+1); fprintf(stderr, "%c", ")]}"[x%3]); } }; // }}} Node *root; RBST() { root = nullptr; } int size() { return root->size(); } int indexOf(T x) { return root->indexOf(x); } T valueAt(int pos) { return root->valueAt(pos); } int lowerBound(T val) { return root->lowerBound(val); } int upperBound(T val) { return root->upperBound(val); } int count(T val) { return root->count(val); } void insert(T val) { if(count(val)) { return; } root = root->insert(val); } void deleteAt(int pos) { root = root->deleteAt(pos); } void deleteValue(T val) { deleteAt(indexOf(val)); } void dump() { root->dump(0); fprintf(stderr, "\n"); } }; template <typename T> class SegTree { size_t n; size_t depth; vector<T> v; void init(size_t m); T query(size_t a, size_t b, size_t k, size_t l, size_t r); T merge(T l, T r); public: const T INVALID = 0; explicit SegTree(size_t m); explicit SegTree(const vector<T> &w); void update(size_t k, T x); // 配列 w の k 番目 (0-indexed) を x にする。 T query(size_t a, size_t b); // [a, b) の範囲で尋ねる。 }; template <typename T> void SegTree<T>:: init(size_t m) { n = 1; depth = 1; while(n < m) { n <<= 1; ++depth; } n = n * 2 - 1; v.assign(n, INVALID); } template <typename T> SegTree<T>::SegTree(size_t m) { init(m); } template <typename T> SegTree<T>::SegTree(const vector<T> &w) { size_t m = w.size(); init(m); for(size_t k=0; k<m; ++k) { update(k, w[k]); } } template <typename T> T SegTree<T>:: merge(T l, T r) { return l + r; } template <typename T> void SegTree<T>:: update(size_t k, T x) { k += (1U << (depth-1)) - 1; v[k] += x; while(k > 0) { k = (k-1) / 2; v[k] = merge(v[k*2+1], v[k*2+2]); } } template <typename T> T SegTree<T>:: query(size_t a, size_t b, size_t k, size_t l, size_t r) { if(r <= a || b <= l) { return INVALID; } if(a <= l && r <= b) { return v[k]; } T vl = query(a, b, k*2+1, l, (l+r)/2), vr = query(a, b, k*2+2, (l+r)/2, r); return merge(vl, vr); } // [a, b) の範囲 (a, b は 0-indexed) template <typename T> T SegTree<T>:: query(size_t a, size_t b) { return query(a, b, 0, 0, (n+1)/2); } int main(void) { int n; scanf("%d", &n); RBST<int> rbst; int ptr = 0; vector<tuple<int, int, int>> v; for(int i=0; i<n; ++i) { int a, b, c; scanf("%d%d%d", &a, &b, &c); v.emplace_back(a, b, c); rbst.insert(b); if(a) { rbst.insert(c); } } SegTree<i64> seg(rbst.size()); i64 res = 0; for(auto tup : v) { int a, b, c; tie(a, b, c) = tup; if(a == 0) { int idx = rbst.indexOf(b); seg.update(idx, c); } else { int idx0 = rbst.indexOf(b), idx1 = rbst.indexOf(c); res += seg.query(idx0, idx1+1); } } printf("%ld\n", res); return 0; }