Contest Duration: ~ (local time) (300 minutes)

Submission #12037260

Source Code Expand

Copy
```#include <bits/stdc++.h>
typedef long long int ll;
#define rep(i, a) for (ll i = 0; i < (a); i++)

using namespace std;

const ll TYPE_MIN = 0;
const ll TYPE_MAX = 1;
const ll TYPE_SUM = 2;
struct LazySegmentTree {
ll n, init;
ll type;
vector<ll> node; // 値配列
vector<ll> lazy; // 遅延配列
vector<bool> isOverride; // 遅延配列の取り扱い（false:加算、true:更新）

LazySegmentTree(ll N, ll init, ll type) : init(init), type(type) {
vector<ll> v(N, init);
n = 1;
while (n < v.size())
n *= 2;
node.resize(2*n-1, init);
lazy.resize(2*n-1, 0);
isOverride.resize(2*n-1, false);
for (ll i=0; i<v.size(); i++)
node[i+n-1] = v[i];
for (ll i=n-2; i>=0; i--) {
switch(type) {
TYPE_MIN:
node[i] = min(node[i*2+1], node[i*2+2]);
break;
TYPE_MAX:
node[i] = max(node[i*2+1], node[i*2+2]);
break;
TYPE_SUM:
node[i] = node[i*2+1] + node[i*2+2];
break;
}
}
}

// k番目のノードを評価する (k=0から順に呼ぶ）
void eval(ll k, ll l, ll r) {
// - 自ノードの値配列に値を伝播
if (isOverride[k]) {
node[k] = lazy[k]; // 区間更新
} else {
node[k] += lazy[k]; // 区間加算
}

// - 子ノードに遅延配列を伝播
if (r - l > 1) {
if (isOverride[k]) {
// 区間更新
switch(type) {
case TYPE_SUM:
node[2*k+1] = lazy[k] / 2;
node[2*k+2] = lazy[k] / 2;
break;
case TYPE_MIN:
case TYPE_MAX:
node[2*k+1] = lazy[k];
node[2*k+2] = lazy[k];
break;
}
isOverride[2*k+1] = true;
isOverride[2*k+2] = true;
} else {
// 区間加算
switch(type) {
case TYPE_SUM:
lazy[2*k+1] += lazy[k] / 2;
lazy[2*k+2] += lazy[k] / 2;
break;
case TYPE_MIN:
case TYPE_MAX:
lazy[2*k+1] += lazy[k];
lazy[2*k+2] += lazy[k];
break;
}
isOverride[2*k+1] = false;
isOverride[2*k+2] = false;
}
}

// - 自ノードの遅延配列を空にする (0を足すという状態にしておく）
lazy[k] = 0;
isOverride[k] = false;
}

void add(ll a, ll b, ll x, ll k=0, ll l=0, ll r=-1) {
if (r < 0)
r = n;

// 範囲外
if (b <= l || r <= a) {
eval(k, l, r);
return;
}

// 完全に含む
if (a <= l && r <= b) {
// 最小値を計算する場合
switch(type) {
case TYPE_MIN:
case TYPE_MAX:
lazy[k] += x;
break;
case TYPE_SUM:
lazy[k] += (r-l) * x;
break;
}
isOverride[k] = false;
eval(k, l, r);
return;
}

// 子ノードに加算して、結果を自ノードに反映する
eval(k, l, r);
add(a, b, x, 2*k+1, l, (l+r)/2);
add(a, b, x, 2*k+2, (l+r)/2, r);
// node[k] = node[2*k+1] + node[2*k+2]; // 区間和なので+
switch(type) {
case TYPE_MIN:
node[k] = min(node[k*2+1], node[k*2+2]);
break;
case TYPE_MAX:
node[k] = max(node[k*2+1], node[k*2+2]);
break;
case TYPE_SUM:
node[k] = node[k*2+1] + node[k*2+2];
break;
}
}

void update(ll a, ll b, ll x, ll k=0, ll l=0, ll r=-1) {
if (r < 0)
r = n;

// 遅延評価
eval(k, l, r);

// 範囲外
if (b <= l || r <= a)
return;

// 完全に含む
if (a <= l && r <= b) {
switch(type) {
case TYPE_MIN:
case TYPE_MAX:
lazy[k] = x;
break;
case TYPE_SUM:
lazy[k] = (r-l) * x;
break;
}
isOverride[k] = true;
eval(k, l, r);
return;
}

// 子ノードに更新して、結果を自ノードに反映する
update(a, b, x, 2*k+1, l, (l+r)/2);
update(a, b, x, 2*k+2, (l+r)/2, r);
//node[k] = node[2*k+1] + node[2*k+2]; // 区間和なので+
switch(type) {
case TYPE_MIN:
node[k] = min(node[k*2+1], node[k*2+2]);
break;
case TYPE_MAX:
node[k] = max(node[k*2+1], node[k*2+2]);
break;
case TYPE_SUM:
node[k] = node[k*2+1] + node[k*2+2];
break;
}
}

ll query(ll a, ll b, ll k=0, ll l=0, ll r=-1) {
if (r < 0)
r = n;
if (b <= l || r <= a)
return init;

eval(k, l, r);
if (a <= l && r <= b)
return node[k];
ll vl = query(a, b, 2*k+1, l, (l+r)/2);
ll vr = query(a, b, 2*k+2, (l+r)/2, r);
switch(type) {
case TYPE_MIN: return min(vl, vr);
case TYPE_MAX: return max(vl, vr);
case TYPE_SUM: return vl + vr;
}
}

static void test() {
{
LazySegmentTree st(5, 0, TYPE_SUM);
rep(i, 5)
st.update(i, i+1, i+1);
assert(st.query(0, 5) == 15);
st.add(1,4,10);
assert(st.query(0, 5) == 45);
st.update(1,3,10);
assert(st.query(0, 5) == 40);
}
{
LazySegmentTree st(5, 0, TYPE_SUM);
rep(i, 5)
st.update(i, i+1, i+1);
assert(st.query(0, 5) == 15);
st.update(1,3,10);
assert(st.query(0, 5) == 30);
st.add(1,4,10);
assert(st.query(0, 5) == 60);
}
{
LazySegmentTree st(5, 100000000, TYPE_MIN);
rep(i, 5)
st.update(i, i+1, i+1);
assert(st.query(0, 5) == 1);
st.add(0,1,5);
assert(st.query(0, 5) == 2);
st.update(1,3,5);
assert(st.query(0, 5) == 4);
}
{
LazySegmentTree st(5, 100000000, TYPE_MIN);
rep(i, 5)
st.update(i, i+1, i+1);
assert(st.query(0, 5) == 1);
st.update(0,2,5);
assert(st.query(0, 5) == 3);
st.add(2,3,5);
assert(st.query(0, 5) == 4);
}
}
};

ll N, M;
LazySegmentTree st(3000000, 0, TYPE_MAX);
vector<pair<ll, ll>> blocks[3000000];

signed main() {
LazySegmentTree::test();
cin >> N >> M;
rep(i, M){
ll l, r, a;
cin >> l >> r >> a;
blocks[r].push_back({l, a});
}
for (ll i=1; i<=N; i++) {
ll m = st.query(0, i);
st.update(i, i+1, m);
for (auto b : blocks[i]) {
st.add(b.first, i+1, b.second);
}
}
//for (int i=0; i<=N+1; i++) {
//  printf("seg[%d] = %d\n", i, st.query(i, i+1));
//}
//rep(i, st.node.size()) {
//  printf("node[%d] = %d\n", i, st.node[i]);
//}

cout << st.query(0, N+1) << endl;
return 0;
}
```

#### Submission Info

Submission Time 2020-04-18 16:41:18+0900 W - Intervals bobuhiro11 C++14 (GCC 5.4.1) 100 6812 Byte AC 739 ms 210928 KB

#### Judge Result

Set Name All
Score / Max Score 100 / 100
Status
 AC × 21
Set Name Test Cases
All 0_00, 0_01, 0_02, 0_03, 0_04, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15
Case Name Status Exec Time Memory
0_00 68 ms 202608 KB
0_01 68 ms 202608 KB
0_02 68 ms 202608 KB
0_03 67 ms 202608 KB
0_04 67 ms 202608 KB
1_00 372 ms 209904 KB
1_01 366 ms 209904 KB
1_02 672 ms 210928 KB
1_03 679 ms 209904 KB
1_04 603 ms 208880 KB
1_05 587 ms 208880 KB
1_06 599 ms 208880 KB
1_07 578 ms 208880 KB
1_08 706 ms 207856 KB
1_09 716 ms 207856 KB
1_10 719 ms 207856 KB
1_11 706 ms 207856 KB
1_12 739 ms 207856 KB
1_13 709 ms 207856 KB
1_14 714 ms 207856 KB
1_15 717 ms 207856 KB