結果
問題 | No.789 範囲の合計 |
ユーザー | T1610 |
提出日時 | 2019-03-17 02:40:04 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 420 ms / 1,000 ms |
コード長 | 3,280 bytes |
コンパイル時間 | 1,755 ms |
コンパイル使用メモリ | 177,824 KB |
実行使用メモリ | 32,256 KB |
最終ジャッジ日時 | 2024-07-05 04:47:57 |
合計ジャッジ時間 | 5,468 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 375 ms
29,184 KB |
testcase_03 | AC | 95 ms
6,944 KB |
testcase_04 | AC | 362 ms
27,904 KB |
testcase_05 | AC | 249 ms
30,208 KB |
testcase_06 | AC | 286 ms
29,696 KB |
testcase_07 | AC | 85 ms
6,944 KB |
testcase_08 | AC | 197 ms
15,872 KB |
testcase_09 | AC | 182 ms
14,720 KB |
testcase_10 | AC | 420 ms
32,256 KB |
testcase_11 | AC | 281 ms
27,904 KB |
testcase_12 | AC | 288 ms
28,032 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) REP(i,0,n) #define REP(i,s,e) for(int i=(s); i<(int)(e); i++) #define repr(i, n) REPR(i, n, 0) #define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--) #define pb push_back #define all(r) r.begin(),r.end() #define rall(r) r.rbegin(),r.rend() #define fi first #define se second typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int INF = 1e9; const ll MOD = 1e9 + 7; double EPS = 1e-8; using ull = unsigned long long; constexpr ll initVal = 0LL; //TODO: fix type and value constexpr ll initLazy = 0LL; //TODO: fix type and value template <typename T> struct Node { T val; T lazy; ull l, r; Node<T>* l_node = nullptr; Node<T>* r_node = nullptr; Node(ull l, ull r, const T& val = initVal) : l(l), r(r), val(val), lazy(initLazy) {} T getVal() { return val + lazy * (r - l); //TODO: fix } T f1(const T& a, const T& b) { return a+b; //TODO: fix } T f2(const T& a, const T& b) { return a+b; //TODO: fix } void push() { if(r - l > 1) { auto m = (l+r)/2; { if(l_node == nullptr) l_node = new Node(l, m); if(lazy != initLazy) l_node->lazy = f2(l_node->lazy, this->lazy); } { if(r_node == nullptr) r_node = new Node(m, r); if(lazy != initLazy) r_node->lazy = f2(r_node->lazy, this->lazy); } } val = getVal(); lazy = initLazy; } void fix() { if(r - l == 1) return; val = f1(l_node->getVal(), r_node->getVal()); } T query(ull qL, ull qR) { if(qR <= l || r <= qL) return initVal; if(qL <= l && r <= qR) return getVal(); if(r - l == 1) return getVal(); push(); T l_val = l_node->query(qL, qR), r_val = r_node->query(qL, qR); return f1(l_val, r_val); } void update(ull uL, ull uR, const T& uVal) { if(uR <= l || r <= uL) return; if(uL <= l && r <= uR) lazy = f2(lazy, uVal); else { push(); l_node->update(uL, uR, uVal); r_node->update(uL, uR, uVal); fix(); } } }; template <typename T> struct DynamicLazySegTree { Node<T> root; DynamicLazySegTree(ull l, ull r, const T& val) : root(l, r, val) {} T query(ull l, ull r) { return root.query(l, r); } void update(ull l, ull r, const T& val) { root.update(l, r, val); } }; int main(){ int n; cin >>n; vi q(n), x(n), y(n); rep(i, n) cin >> q[i] >> x[i] >> y[i]; map<int, int> mp; rep(i, n) { mp[x[i]] = 1; mp[y[i]] = 1; } { int cnt = 0; for(auto && p : mp) p.se = cnt++; } int m = mp.size(); DynamicLazySegTree<ll> seg(0, m+1, 0LL); ll ans = 0LL; rep(i, n) { if(q[i] == 0) { int j = mp[x[i]]; seg.update(j, j+1, y[i]); } else { int j = mp[x[i]], k = mp[y[i]]+1; ans += seg.query(j, k); } } cout << ans << endl; return 0; }