結果
| 問題 | No.789 範囲の合計 |
| ユーザー |
 rogi52
|
| 提出日時 | 2023-10-19 17:17:13 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 76 ms / 1,000 ms |
| コード長 | 10,781 bytes |
| コンパイル時間 | 2,147 ms |
| コンパイル使用メモリ | 207,252 KB |
| 実行使用メモリ | 6,656 KB |
| 最終ジャッジ日時 | 2024-09-19 13:36:37 |
| 合計ジャッジ時間 | 4,611 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 72 ms
5,888 KB |
| testcase_03 | AC | 49 ms
5,376 KB |
| testcase_04 | AC | 76 ms
6,144 KB |
| testcase_05 | AC | 60 ms
5,760 KB |
| testcase_06 | AC | 62 ms
5,888 KB |
| testcase_07 | AC | 40 ms
5,376 KB |
| testcase_08 | AC | 58 ms
6,656 KB |
| testcase_09 | AC | 53 ms
6,272 KB |
| testcase_10 | AC | 69 ms
5,376 KB |
| testcase_11 | AC | 49 ms
6,144 KB |
| testcase_12 | AC | 48 ms
6,144 KB |
| testcase_13 | AC | 2 ms
5,376 KB |
| testcase_14 | AC | 2 ms
5,376 KB |
ソースコード
#line 1 "sparse_segtree.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/789"
#line 2 "/Users/korogi/Desktop/cp-library-2/src/cp-template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using i128 = __int128_t;
template < class T > bool chmin(T& a, T b) { if(a > b) { a = b; return true; } return false; }
template < class T > bool chmax(T& a, T b) { if(a < b) { a = b; return true; } return false; }
#line 2 "/Users/korogi/Desktop/cp-library-2/src/utility/rep_itr.hpp"
template < class T > struct itr {
T i, d;
constexpr itr(const T i) noexcept : i(i), d(1) {}
constexpr itr(const T i, const T d) noexcept : i(i), d(d) {}
void operator++() noexcept { i += d; }
constexpr int operator*() const noexcept { return i; }
constexpr bool operator!=(const itr x) const noexcept {
return d > 0 ? i < x.i : i > x.i;
}
};
template < class T > struct rep {
const itr< T > s, t;
constexpr rep(const T t) noexcept : s(0), t(t) {}
constexpr rep(const T s, const T t) noexcept : s(s), t(t) {}
constexpr rep(const T s, const T t, const T d) noexcept : s(s, d), t(t, d) {}
constexpr auto begin() const noexcept { return s; }
constexpr auto end() const noexcept { return t; }
};
template < class T > struct revrep {
const itr < T > s, t;
constexpr revrep(const T t) noexcept : s(t - 1, -1), t(-1, -1) {}
constexpr revrep(const T s, const T t) noexcept : s(t - 1, -1), t(s - 1, -1) {}
constexpr revrep(const T s, const T t, const T d) noexcept : s(t - 1, -d), t(s - 1, -d) {}
constexpr auto begin() const noexcept { return s; }
constexpr auto end() const noexcept { return t; }
};
#line 2 "/Users/korogi/Desktop/cp-library-2/src/utility/io.hpp"
namespace scanner {
struct sca {
template < class T > operator T() {
T s; cin >> s; return s;
}
};
struct vec {
int n;
vec(int n) : n(n) {}
template < class T > operator vector< T >() {
vector< T > v(n);
for(T& x : v) cin >> x;
return v;
}
};
struct mat {
int h,w;
mat(int h, int w) : h(h), w(w) {}
template < class T > operator vector< vector< T > >() {
vector m(h, vector< T >(w));
for(vector< T >& v : m) for(T& x : v) cin >> x;
return m;
}
};
struct speedup {
speedup() {
cin.tie(0);
ios::sync_with_stdio(0);
}
} su;
}
scanner::sca in() { return scanner::sca(); }
scanner::vec in(int n) { return scanner::vec(n); }
scanner::mat in(int h, int w) { return scanner::mat(h, w); }
namespace printer {
void precision(int d) {
cout << fixed << setprecision(d);
}
void flush() {
cout.flush();
}
}
int print() { cout << '\n'; return 0; }
template < class head, class... tail > int print(head&& h, tail&&... t) {
cout << h; if(sizeof...(tail)) cout << ' ';
return print(forward<tail>(t)...);
}
template < class T > int print(vector< T > a, char sep = ' ') {
int n = a.size();
for(int i : rep(n)) cout << a[i] << (i != n - 1 ? sep : '\n');
return 0;
}
template < class T > int print(vector< vector< T > > a) {
if(a.empty()) return 0;
int h = a.size(), w = a[0].size();
for(int i : rep(h)) for(int j : rep(w)) cout << a[i][j] << (j != w - 1 ? ' ' : '\n');
return 0;
}
#line 2 "/Users/korogi/Desktop/cp-library-2/src/utility/key_val.hpp"
template < class K, class V >
struct key_val {
K key; V val;
key_val() {}
key_val(K key, V val) : key(key), val(val) {}
};
#line 2 "/Users/korogi/Desktop/cp-library-2/src/utility/vec_op.hpp"
template < class T >
key_val< int, T > max_of(const vector< T >& a) {
int i = max_element(a.begin(), a.end()) - a.begin();
return {i, a[i]};
}
template < class T >
key_val< int, T > min_of(const vector< T >& a) {
int i = min_element(a.begin(), a.end()) - a.begin();
return {i, a[i]};
}
template < class T >
T sum_of(const vector< T >& a) {
T sum = 0;
for(const T x : a) sum += x;
return sum;
}
template < class T >
vector<int> freq_of(const vector< T >& a, T L, T R) {
vector<int> res(R - L);
for(const T x : a) res[x - L]++;
return res;
}
template < class T >
vector<int> freq_of(const vector< T >& a, T R) {
return freq_of(a, T(0), R);
}
template < class T >
struct prefix_sum {
vector< T > s;
prefix_sum(const vector< T >& a) : s(a) {
s.insert(s.begin(), T(0));
for(int i : rep(a.size())) s[i + 1] += s[i];
}
// [L, R)
T sum(int L, int R) {
return s[R] - s[L];
}
};
#line 16 "/Users/korogi/Desktop/cp-library-2/src/cp-template.hpp"
#line 1 "/Users/korogi/Desktop/cp-library-2/src/algorithm/bin_search.hpp"
template < class T, class F >
T bin_search(T ok, T ng, F& f) {
while(abs(ok - ng) > 1) {
T mid = (ok + ng) / 2;
(f(mid) ? ok : ng) = mid;
}
return ok;
}
template < class T, class F >
T bin_search_real(T ok, T ng, F& f, int step = 80) {
while(step--) {
T mid = (ok + ng) / 2;
(f(mid) ? ok : ng) = mid;
}
return ok;
}
#line 2 "/Users/korogi/Desktop/cp-library-2/src/algorithm/argsort.hpp"
template < class T > std::vector< int > argsort(const std::vector< T > &a) {
std::vector< int > ids((int)a.size());
std::iota(ids.begin(), ids.end(), 0);
std::sort(ids.begin(), ids.end(), [&](int i, int j) {
return a[i] < a[j] || (a[i] == a[j] && i < j);
});
return ids;
}
#line 2 "/Users/korogi/Desktop/cp-library-2/src/data_structure/sparse_segtree.hpp"
template < class I, class monoid > struct sparse_segtree {
using S = typename monoid::set;
struct node {
I index;
S value, prod;
std::unique_ptr< node > left, right;
node(I index, S value) : index(index), value(value), prod(value), left(nullptr), right(nullptr) {}
void update() {
prod = monoid::op(monoid::op(left ? left ->prod : monoid::id(), value), right ? right->prod : monoid::id());
}
};
using node_ptr = std::unique_ptr< node >;
I n;
node_ptr root;
sparse_segtree() {}
sparse_segtree(I n) : n(n), root(nullptr) {}
void set(I i, S x) {
assert(0 <= i and i < n);
set(root, 0, n, i, x);
}
S get(I i) {
assert(0 <= i and i < n);
return get(root, 0, n, i);
}
S prod(I l, I r) {
assert(0 <= l and l <= r and r <= n);
return prod(root, 0, n, l, r);
}
S all_prod() {
return root ? root->prod : monoid::id();
}
void reset(I l, I r) {
assert(0 <= l and l <= r and r <= n);
return reset(root, 0, n, l, r);
}
template < class func >
I max_right(I l, func f) {
assert(0 <= l and l <= n);
S prod = monoid::id();
assert(f(prod));
return max_right(root, 0, n, l, f, prod);
}
template < class func >
I min_left(I r, func f) {
assert(0 <= r and r <= n);
S prod = monoid::id();
assert(f(prod));
return min_left(root, 0, n, r, f, prod);
}
private:
void set(node_ptr& t, I a, I b, I p, S x) {
if(!t) {
t = std::make_unique< node >(p, x);
return;
}
if(t->index == p) {
t->value = x;
t->update();
return;
}
I m = (a + b) / 2;
if(p < m) {
if(t->index < p) std::swap(t->index, p), std::swap(t->value, x);
set(t->left , a, m, p, x);
} else {
if(p < t->index) std::swap(p, t->index), std::swap(x, t->value);
set(t->right, m, b, p, x);
}
t->update();
}
S get(const node_ptr& t, I a, I b, I i) {
if(!t) return monoid::id();
if(t->index == i) return t->value;
I m = (a + b) / 2;
if(i < m)
return get(t->left , a, m, i);
else
return get(t->right, m, b, i);
}
S prod(const node_ptr& t, I a, I b, I l, I r) {
if(!t or b <= l or r <= a) return monoid::id();
if(l <= a and b <= r) return t->prod;
I m = (a + b) / 2;
S res = prod(t->left, a, m, l, r);
if(l <= t->index and t->index < r) res = monoid::op(res, t->value);
return monoid::op(res, prod(t->right, m, b, l, r));
}
void reset(node_ptr& t, I a, I b, I l, I r) {
if(!t or b <= l or r <= a) return;
if(l <= a and b <= r) {
t.reset();
return;
}
I m = (a + b) / 2;
reset(t->left , a, m, l, r);
reset(t->right, m, b, l, r);
t->update();
}
template < class func >
I max_right(const node_ptr& t, I a, I b, I l, const func& f, S& prod) {
if(!t or b <= l) return n;
if(f(monoid::op(prod, t->prod))) {
prod = monoid::op(prod, t->prod);
return n;
}
I m = (a + b) / 2;
I res = max_right(t->left, a, m, l, f, prod);
if(res != n) return res;
if(l <= t->index) {
prod = monoid::op(prod, t->value);
if(not f(prod)) return t->index;
}
return max_right(t->right, m, b, l, f, prod);
}
template < class func >
I min_left(const node_ptr& t, I a, I b, I r, const func& f, S& prod) {
if(!t or r <= a) return 0;
if(f(monoid::op(t->prod, prod))) {
prod = monoid::op(t->prod, prod);
return 0;
}
I m = (a + b) / 2;
I res = min_left(t->right, m, b, r, f, prod);
if(res != 0) return res;
if(t->index < r) {
prod = monoid::op(t->value, prod);
if(not f(prod)) return t->index + 1;
}
return min_left(t->left, a, m, r, f, prod);
}
};
#line 1 "/Users/korogi/Desktop/cp-library-2/src/algebra/sum.hpp"
template < class T > class sum_monoid {
public:
using set = T;
static constexpr T op(const T &l, const T &r) { return l + r; }
static constexpr T id() { return T(0); }
static constexpr T inv(const T &x) { return -x; }
static constexpr T pow(const T &x, const ll n) { return x * n; }
static constexpr bool comm = true;
};
#line 6 "sparse_segtree.test.cpp"
int main() {
const int M = 1'000'000'001;
sparse_segtree< int, sum_monoid<int> > seg(M);
int n = in();
ll ans = 0;
for(int _n : rep(n)) {
int t = in();
if(t == 0) {
int x = in(), y = in();
seg.set(x, seg.get(x) + y);
}
if(t == 1) {
int l = in(), r = in(); r++;
ans += seg.prod(l, r);
}
}
print(ans);
}