結果
問題 | No.789 範囲の合計 |
ユーザー | NyaanNyaan |
提出日時 | 2020-06-16 15:30:25 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 132 ms / 1,000 ms |
コード長 | 7,888 bytes |
コンパイル時間 | 1,488 ms |
コンパイル使用メモリ | 171,172 KB |
実行使用メモリ | 27,216 KB |
最終ジャッジ日時 | 2024-07-03 11:52:13 |
合計ジャッジ時間 | 4,086 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 132 ms
23,436 KB |
testcase_03 | AC | 65 ms
6,944 KB |
testcase_04 | AC | 130 ms
25,608 KB |
testcase_05 | AC | 111 ms
22,292 KB |
testcase_06 | AC | 112 ms
24,216 KB |
testcase_07 | AC | 60 ms
6,940 KB |
testcase_08 | AC | 103 ms
27,216 KB |
testcase_09 | AC | 103 ms
25,436 KB |
testcase_10 | AC | 132 ms
16,416 KB |
testcase_11 | AC | 96 ms
22,252 KB |
testcase_12 | AC | 100 ms
23,972 KB |
testcase_13 | AC | 2 ms
6,940 KB |
testcase_14 | AC | 2 ms
6,940 KB |
ソースコード
#pragma region kyopro_template #include <bits/stdc++.h> #define pb push_back #define eb emplace_back #define fi first #define se second #define each(x, v) for (auto &x : v) #define all(v) (v).begin(), (v).end() #define sz(v) ((int)(v).size()) #define mem(a, val) memset(a, val, sizeof(a)) #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define inc(...) \ char __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) using namespace std; void solve(); using ll = long long; template <class T = ll> using V = vector<T>; using vi = vector<int>; using vl = vector<long long>; using vvi = vector<vector<int>>; using vd = V<double>; using vs = V<string>; using vvl = vector<vector<long long>>; using P = pair<long long, long long>; using vp = vector<P>; using pii = pair<int, int>; using vpi = vector<pair<int, int>>; constexpr int inf = 1001001001; constexpr long long infLL = (1LL << 61) - 1; template <typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template <typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template <typename T, typename U> ll ceil(T a, U b) { return (a + b - 1) / b; } constexpr ll TEN(int n) { ll ret = 1, x = 10; while (n) { if (n & 1) ret *= x; x *= x; n >>= 1; } return ret; } template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; } template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.first >> p.second; return is; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; } void in() {} template <typename T, class... U> void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template <typename T, class... U> void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << " "; out(u...); } template <typename T> void die(T x) { out(x); exit(0); } #ifdef NyaanDebug #include "NyaanDebug.h" #define trc(...) \ do { \ cerr << #__VA_ARGS__ << " = "; \ dbg_out(__VA_ARGS__); \ } while (0) #define trca(v, N) \ do { \ cerr << #v << " = "; \ array_out(v, N); \ } while (0) #define trcc(v) \ do { \ cerr << #v << " = {"; \ each(x, v) { cerr << " " << x << ","; } \ cerr << "}" << endl; \ } while (0) #else #define trc(...) #define trca(...) #define trcc(...) int main() { solve(); } #endif /*struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya;*/ inline int popcnt(unsigned long long a) { return __builtin_popcountll(a); } inline int lsb(unsigned long long a) { return __builtin_ctzll(a); } inline int msb(unsigned long long a) { return 63 - __builtin_clzll(a); } template <typename T> inline int getbit(T a, int i) { return (a >> i) & 1; } template <typename T> inline void setbit(T &a, int i) { a |= (1LL << i); } template <typename T> inline void delbit(T &a, int i) { a &= ~(1LL << i); } template <typename T> int lb(const vector<T> &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template <typename T> int ub(const vector<T> &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } template <typename T> vector<T> mkrui(const vector<T> &v) { vector<T> ret(v.size() + 1); for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; return ret; }; template <typename T> vector<T> mkuni(const vector<T> &v) { vector<T> ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template <typename F> vector<int> mkord(int N, F f) { vector<int> ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template <typename T = int> vector<T> mkiota(int N) { vector<T> ret(N); iota(begin(ret), end(ret), 0); return ret; } #pragma endregion constexpr int MOD = 998244353; template <typename T, typename F, int NODES = 4194304> struct DynamicSegmentTree { using ll = long long; struct Node { T data; Node *l, *r; Node() {} Node(const T &_data) : data(_data), l(nullptr), r(nullptr) {} }; Node *pool; int pid; ll L,R; const F &f; const T ID; Node *root; DynamicSegmentTree(const vector<T> &v, const F &_f, const T &_ID) : pid(0), L(0), R((ll)v.size()), f(_f), ID(_ID) { pool = new Node[NODES]; root = build(v); } DynamicSegmentTree(const ll &_L, const ll &_R, const F &_f, const T &_ID) : pid(0), L(_L), R(_R), f(_f), ID(_ID) { pool = new Node[NODES]; root = my_new(ID); } Node *my_new(const T &data) { pool[pid].data = data; pool[pid].l = pool[pid].r = nullptr; return &(pool[pid++]); } Node *my_new(Node *l, Node *r) { pool[pid].data = f(l->data, r->data); pool[pid].l = l; pool[pid].r = r; return &(pool[pid++]); } Node *build(const vector<T> &v) { return build(L, R, v); } Node *build(ll l, ll r, const vector<T> &v) { if (l + 1 == r) return my_new(v[l]); ll m = (l + r) >> 1; return my_new(build(l, m, v), build(m, r, v)); } void _update(ll a, const T &x, Node *n, ll l, ll r) { if (l + 1 == r) { n->data = x; return; } ll m = (l + r) >> 1; if (a < m) { if (!n->l) n->l = my_new(ID); _update(a, x, n->l, l, m); } else { if (!n->r) n->r = my_new(ID); _update(a, x, n->r, m, r); } n->data = f(n->l ? (n->l)->data : ID, n->r ? (n->r)->data : ID); } void update(ll k, const T &x) { _update(k, x, root, L, R); } void add(ll k, const T &x) { Node *n = root; ll l = L, r = R; n->data = f(n->data, x); while (r - l > 1) { ll m = (l + r) >> 1; if (k < m) { if (!n->l) n->l = my_new(ID); n = n->l; r = m; } else { if (!n->r) n->r = my_new(ID); n = n->r; l = m; } n->data = f(n->data, x); } } T _query(ll a, ll b, Node *n, ll l, ll r) { if (r <= a or b <= l) return ID; if (a <= l and r <= b) return n->data; ll m = (l + r) >> 1; return f(n->l ? _query(a, b, n->l, l, m) : ID, n->r ? _query(a, b, n->r, m, r) : ID); } T query(ll a, ll b) { return _query(a, b, root, L, R); } }; void solve() { ini(N); auto f = [](ll a,ll b){return a+b;}; DynamicSegmentTree<ll,decltype(f)> seg(0,inf,f,0); ll ans = 0; rep(_,N){ inl(c,x,y); if(c == 0){ seg.add(x,y); } else{ ans += seg.query(x,y+1); } } out(ans); }