結果
問題 | No.230 Splarraay スプラレェーイ |
ユーザー | ojisan_IT |
提出日時 | 2018-06-14 17:02:10 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 145 ms / 5,000 ms |
コード長 | 3,663 bytes |
コンパイル時間 | 1,680 ms |
コンパイル使用メモリ | 174,732 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-30 14:24:19 |
合計ジャッジ時間 | 3,386 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
6,816 KB |
testcase_01 | AC | 4 ms
6,940 KB |
testcase_02 | AC | 4 ms
6,940 KB |
testcase_03 | AC | 4 ms
6,944 KB |
testcase_04 | AC | 4 ms
6,944 KB |
testcase_05 | AC | 5 ms
6,940 KB |
testcase_06 | AC | 12 ms
6,940 KB |
testcase_07 | AC | 5 ms
6,940 KB |
testcase_08 | AC | 6 ms
6,940 KB |
testcase_09 | AC | 71 ms
6,944 KB |
testcase_10 | AC | 81 ms
6,940 KB |
testcase_11 | AC | 44 ms
6,940 KB |
testcase_12 | AC | 72 ms
6,940 KB |
testcase_13 | AC | 15 ms
6,944 KB |
testcase_14 | AC | 74 ms
6,940 KB |
testcase_15 | AC | 94 ms
6,940 KB |
testcase_16 | AC | 126 ms
6,940 KB |
testcase_17 | AC | 145 ms
6,940 KB |
testcase_18 | AC | 95 ms
6,940 KB |
testcase_19 | AC | 90 ms
6,940 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; template<class T> using vt = vector<T>; template<class T> using vvt = vector<vt<T>>; template<class T> using ttt = tuple<T,T>; using tii = tuple<int,int>; using vi = vector<int>; #define rep(i,n) for(int i=0;i<(int)(n);i++) #define pb push_back #define mt make_tuple #define ALL(a) (a).begin(),(a).end() #define FST first #define SEC second #define DEB cerr<<"!"<<endl #define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl #define DIV int(1e9+7) const int INF = (INT_MAX/2); const ll LLINF = (LLONG_MAX/2); const double eps = 1e-8; //const double PI = M_PI; inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;} inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;} /*Coding Space*/ // ペアの全探索は a.begin(), a.begin() + n/2, a.end() として a[i],a[i+n/2](i = 0..n/2) // This Segtree written by @qcw_pro(Retirement Maximum member). template <class M, class O> // M: monoid, O: operator monoid struct SegTree { using MM = function <M(M, M)>; using MO = function <M(M, O)>; using OO = function <O(O, O)>; using OI = function <O(O, int)>; const int n, h; // n: array size, h: height of tree const M m_id; // identity element of monoid const O o_id; // identity element of operator monoid MM mm; MO mo; OO oo; OI oi; vector<M> m; // monoid array vector<O> o; // operator monoid array SegTree(int n, M m_id, O o_id, MM mm, MO mo, OO oo, OI oi = [](const O& a, int b) { return a; }) :n(n), h(sizeof(int)*CHAR_BIT - __builtin_clz(n)), m_id(m_id), o_id(o_id), mm(mm), mo(mo), oo(oo), oi(oi), m(n * 2, m_id), o(n * 2, o_id) {} inline void apply(int i, const O& v, int k) { m[i] = mo(m[i], oi(v, k)); if(i < n) o[i] = oo(o[i], v); } inline void build(int i) { while(i >>= 1) if(o[i] == o_id) m[i] = mm(m[i * 2], m[i * 2 + 1]); } inline void push(int i) { int s{ i >> h ? h : h - 1 }; for(int k{ 1 << (s - 1) }; s > 0; --s, k >>= 1) { int p{ i >> s }; if(o[p] == o_id) continue; apply(p * 2, o[p], k); apply(p * 2 + 1, o[p], k); o[p] = o_id; } } void modify(int l, int r, const O& v) { // [l,r) 変更クエリ l += n, r += n; push(l), push(r - 1); int ll{ l }, rr{ r }; for(int k{ 1 }; l < r; l >>= 1, r >>= 1, k <<= 1) { if(l & 1) apply(l++, v, k); if(r & 1) apply(r - 1, v, k); } build(ll), build(rr - 1); } M query(int l, int r) { // [l,r) 出力クエリ l += n, r += n; push(l), push(r - 1); M a{ m_id }, b{ m_id }; for(; l < r; l >>= 1, r >>= 1) { if(l & 1) a = mm(a, m[l++]); if(r & 1) b = mm(m[r - 1], b); } return mm(a, b); } }; //SegTree<input type, operator type> (size, M_I, O_I, MM, MO, OO, (OI)) const ll m_id = 0; const ll o_id = 10000; SegTree<ll, ll> a(100001, m_id, o_id, plus<ll>(), [](const ll a, const ll b) { return b; }, [](const ll a, const ll b) { return b; }, [](const ll a, const int k) { return (a == o_id)? a:a * k; }); int main(){ int n,q; cin >> n >>q; ll ans_a = 0; ll ans_b = 0; rep(i,q){ int x,l,r; cin >> x >> l >> r; if(x == 1){ a.modify(l,++r,1); }else if(x == 2){ a.modify(l,++r,1000000); }else{ ll aq = a.query(l,++r); ll aa = aq % 1000000; ll bb = aq / 1000000; if(aa < bb) ans_b += bb; if(aa > bb) ans_a += aa; } } ll aq = a.query(0,n); ll aa = aq % 1000000; ll bb = aq / 1000000; cout << ans_a + aa << " " << ans_b + bb << endl; }