結果
問題 |
No.789 範囲の合計
|
ユーザー |
|
提出日時 | 2025-06-30 10:57:19 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 57 ms / 1,000 ms |
コード長 | 1,035 bytes |
コンパイル時間 | 3,794 ms |
コンパイル使用メモリ | 294,844 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-06-30 10:57:25 |
合計ジャッジ時間 | 6,274 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #include <atcoder/fenwicktree> using namespace atcoder; template<typename S, typename T> struct CompressedBIT { private: fenwick_tree<T> f; vector<S> p; int id(S x) const { return ranges::lower_bound(p, x) - p.begin(); } public: CompressedBIT() = default; CompressedBIT(int N) { p.reserve(N); } void use(S x) { p.emplace_back(x); } void build() { ranges::sort(p); p.erase(unique(p.begin(), p.end()), p.end()); f = fenwick_tree<T>(p.size()); } void add(S i, T x) { f.add(id(i), x); } T sum(S l, S r) { return f.sum(id(l), id(r)); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll N; cin >> N; CompressedBIT<ll, ll> S; vector<tuple<ll, ll, ll>> Q(N); for(auto &[type, l, r] : Q) { cin >> type >> l >> r; if(!type) { S.use(l); } } S.build(); ll ans = 0; for(auto &[type, l, r] : Q) { if(!type) { S.add(l, r); } else { ans += S.sum(l, ++r); } } cout << ans << "\n"; }