ABC 17 C - ハイスコア ( Imosu or Segment Tree )

C: ハイスコア - AtCoder Beginner Contest 017 | AtCoder
Basically we would like to find the element that is covered with the least cost. It is intuitive to use segment tree, but actually we could use imosu algorithm to maintain the difference of adjacent elements in O( 1 ) and query in O( n ) in the end.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
const int MAXS = 5e3 + 3;
const int INF = 0x3f3f3f3f;

int n, m;
int l[ MAXN ], r[ MAXN ], s[ MAXN ];
int sum;

int seg[ MAXM ];

void solve(){
    for(int i = 0; i < n; ++i){
        seg[ l[ i ] ] += s[ i ];
        seg[ r[ i ] + 1 ] -= s[ i ];
    }
    int minv = INF;
    for(int i = 1; i <= m; ++i){
        seg[ i ] += seg[ i - 1 ];
        minv = min<int>( minv, seg[ i ] );
    }
    printf("%d\n", sum - minv);
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i){
        scanf("%d%d%d", &l[ i ], &r[ i ], &s[ i ]);
        sum += s[ i ];
    }
    solve();
    return 0;
}

Segment tree version.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
const int MAXS = 5e3 + 3;
const int INF = 0x3f3f3f3f;

struct itvt{
    int minv, add_tag;
    int lb, rb;
    itvt *lc, *rc;
    itvt():minv(0),add_tag(0),lc(NULL),rc(NULL){}
    void push(){
        lc->minv += add_tag;
        lc->add_tag += add_tag;
        rc->minv += add_tag;
        rc->add_tag += add_tag;
        add_tag = 0;
    }
    void pull(){
        minv = min<int>( lc->minv, rc->minv );
    }
};

itvt* buildItvt(int lb, int rb){
    itvt *t = new itvt();
    t->lb = lb, t->rb = rb;
    if( lb == rb ) return t;
    int mid = lb + rb >> 1;
    t->lc = buildItvt( lb, mid );
    t->rc = buildItvt( mid + 1, rb );
    t->pull();
    return t;
}

void updateItvt(itvt *t, int ql, int qr, int v){
    if( qr < t->lb || t->rb < ql ) return;
    if( ql <= t->lb && t->rb <= qr ){
        t->minv += v;
        t->add_tag += v;
        return;
    }
    t->push();
    updateItvt( t->lc, ql, qr, v );
    updateItvt( t->rc, ql, qr, v );
    t->pull();
}

int n, m;
int l[ MAXN ], r[ MAXN ], s[ MAXN ];
int sum;

void solve(){
    itvt *root = buildItvt( 1, m );
    for(int i = 0; i < n; ++i)
        updateItvt( root, l[ i ], r[ i ], s[ i ] );
    printf("%d\n", sum - root->minv);
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i){
        scanf("%d%d%d", &l[ i ], &r[ i ], &s[ i ]);
        sum += s[ i ];
    }
    solve();
    return 0;
}

Imosu with Fenwick tree.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
const int MAXS = 5e3 + 3;
const int INF = 0x3f3f3f3f;

struct BIT{
    int size;
    int dat[ MAXN ]; // 1 BASE IDX
    void init(int _sz){
        size = _sz;
        memset( dat, 0, sizeof(dat) );
    }
    void update(int x, int v){
        for(int i = x; i <= size; i += i & -i)
            dat[ i ] += v;
    }
    int psum(int x){
        int res = 0;
        for(int i = x; i > 0; i -= i & -i)
            res += dat[ i ];
        return res;
    }
} bit;

int n, m;
int l[ MAXN ], r[ MAXN ], s[ MAXN ];
int sum;

void solve(){
    bit.init( m );
    for(int i = 0; i < n; ++i){
        bit.update( l[ i ], s[ i ] );
        bit.update( r[ i ] + 1, -s[ i ] );
    }
    int minv = INF;
    for(int i = 1; i <= m; ++i)
        minv = min<int>( minv, bit.psum( i ) );
    printf("%d\n", sum - minv);
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i){
        scanf("%d%d%d", &l[ i ], &r[ i ], &s[ i ]);
        sum += s[ i ];
    }
    solve();
    return 0;
}