結果
問題 | No.230 Splarraay スプラレェーイ |
ユーザー |
|
提出日時 | 2016-11-19 02:59:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 177 ms / 5,000 ms |
コード長 | 2,689 bytes |
コンパイル時間 | 1,541 ms |
コンパイル使用メモリ | 172,536 KB |
実行使用メモリ | 7,424 KB |
最終ジャッジ日時 | 2024-11-26 10:53:16 |
合計ジャッジ時間 | 3,834 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int nextpow2(int x, int r = 1) { return r < x ? nextpow2(x, r + r) : r; } template <typename Monoid, typename Lazy> struct LazySegTree { using data_type = typename Monoid::value_type; using lazy_type = typename Lazy::value_type; const int N; const data_type empty = Monoid::empty(); const lazy_type nil = Lazy::empty(); vector<data_type> data; vector<lazy_type> lazy; LazySegTree(int size) : N(nextpow2(size)) { data.assign(N * 2, empty); lazy.assign(N * 2, nil); } inline void propagate(int x, int l, int r) { if (lazy[x] == nil) return; data[x] = Lazy::eval(data[x], lazy[x], l, r); if (x < N - 1) { lazy[x + x + 1] = Lazy::append(lazy[x + x + 1], lazy[x]); lazy[x + x + 2] = Lazy::append(lazy[x + x + 2], lazy[x]); } lazy[x] = nil; } void query(lazy_type v, int a, int b) { query(v, a, b, 0, 0, N); } void query(lazy_type v, int a, int b, int x, int l, int r) { propagate(x, l, r); if (r <= a || b <= l) return; if (a <= l && r <= b) { lazy[x] = Lazy::append(lazy[x], v); propagate(x, l, r); return; } int m = (l + r) / 2; query(v, a, b, x + x + 1, l, m); query(v, a, b, x + x + 2, m, r); data[x] = Monoid::append(data[x + x + 1], data[x + x + 2]); } data_type concat(int a, int b) { return concat(a, b, 0, 0, N); } data_type concat(int a, int b, int x, int l, int r) { propagate(x, l, r); if (r <= a || b <= l) return empty; if (a <= l && r <= b) return data[x]; int m = (l + r) / 2; return Monoid::append(concat(a, b, x + x + 1, l, m), concat(a, b, x + x + 2, m, r)); } }; struct Sum { using value_type = int; static value_type append(value_type x, value_type y) { return x + y; } static value_type empty() { return 0; } struct FillQuery { using value_type = int; static value_type append(value_type x, value_type y) { return y; } static value_type empty() { return -1; } template <typename T> static T eval(T v, value_type x, int l, int r) { return (r - l) * x; } }; }; using ll = long long; int main() { int N, Q; cin >> N >> Q; LazySegTree<Sum, Sum::FillQuery> A{N}, B{N}; ll a = 0, b = 0; for (int q = 0; q < Q; q++) { int x, l, r; cin >> x >> l >> r; r++; if (x == 0) { auto ac = A.concat(l, r); auto bc = B.concat(l, r); if (ac == bc) continue; if (ac < bc) { b += bc; } else { a += ac; } } else { A.query(x == 1, l, r); B.query(x == 2, l, r); } } a += A.concat(0, N); b += B.concat(0, N); cout << a << ' ' << b << endl; }