結果
問題 | No.230 Splarraay スプラレェーイ |
ユーザー |
![]() |
提出日時 | 2015-07-12 22:58:13 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 129 ms / 5,000 ms |
コード長 | 1,721 bytes |
コンパイル時間 | 1,025 ms |
コンパイル使用メモリ | 91,356 KB |
実行使用メモリ | 36,224 KB |
最終ジャッジ日時 | 2024-07-08 06:11:11 |
合計ジャッジ時間 | 2,844 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <complex> #include <queue> #include <set> #include <map> using namespace std; template<int NV> class SegTree_Lazy { public: vector<int> val, to; SegTree_Lazy() { val.resize(NV * 2); to.resize(NV * 2); }; int comp(int l, int r) { return l+r; } int getval(int x, int y, int l = 0, int r = NV, int k = 1) { if(r<=x || y<=l) return 0; if(x<=l && r<=y) return to[k]; x = max(x, l); y = min(y, r); if(val[k] >= 0) return val[k] ? (y-x) : 0; return comp(getval(x, y, l, (l+r) / 2, k*2), getval(x, y, (l+r) / 2, r, k*2+1)); } void update(int x, int y, int v, int l=0, int r=NV, int k=1) { if(l >= r) return; if(x<=l && r<=y) { val[k] = v; to[k] = val[k] ? (r-l) : 0; } else if(l < y && x < r) { if(val[k] != -1) { val[k*2] = val[k*2+1] = val[k]; to[k*2] = to[k*2+1] = val[k] ? (r-l)/2:0; val[k] = -1; } update(x, y, v, l, (l+r)/2, k*2); update(x, y, v, (l+r)/2,r,k*2+1); to[k] = comp(to[k*2], to[k*2+1]); } } }; int N, Q; typedef long long ll; ll AA, BB; SegTree_Lazy<1<<20> st[2]; void solve() { int i, j, k, l, r, x, y; string s; cin >> N >> Q; while(Q--) { cin >> x >> l >> r; if(x == 0) { int a = st[0].getval(l, r+1); int b = st[1].getval(l, r+1); if(a > b) AA += a; if(a < b) BB += b; } else { st[x-1].update(l, r+1, 1); st[(x-1)^1].update(l, r+1, 0); } } AA += st[0].getval(0, N); BB += st[1].getval(0, N); printf("%lld %lld\n", AA, BB); } int main() { solve(); return 0; }