VOMARIO – SPOJ

Đề bài: http://vn.spoj.com/problems/VOMARIO/

Thuận toán: Sử dụng Interval Tree để quản lí tập các đoạn thẳng. Có thể dễ dàng tìm được công thức QHĐ O(N^2) với F(i) = số năng lượng max đến lượt chơi thứ i. Để giảm độ phức tạp thì có thể dùng IT để cập nhật nhanh.

Code:

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 2;
const int INF = 1e9 + 7;
 
using namespace std;
int n;
long long x[MAXN], w[MAXN], e[MAXN], a[MAXN], v[MAXN], b[MAXN];
long long f[MAXN];
struct line{
    long long a, b;
} it[MAXN * 4];
long long Get(line d, long long pos)
{
    return d.a * v[pos] + d.b;
}
 
long long query(int x, int l, int r, long long pos)
{
    //cout << it[x].a<<" "<<it[x].b<<" :"<<l<<" "<<r<<endl;
    if (pos < l || pos > r) return 0;
    long long ans = Get(it[x], pos);
    if (l == r) return ans;
    int mid = (l + r) / 2;
    ans = max(ans, query(2 * x, l, mid, pos));
    ans = max(ans, query(2 * x + 1, mid + 1, r, pos));
    return ans;
}
 
void update(int x, int l, int r, int u, int v, line val)
{
    int mid = (l + r) / 2;
    if (r < u || v < l) return;
    if (u <= l && r <= v){
    // do something
    if (Get(it[x], l) >= Get(val, l) && Get(it[x], r) >= Get(val, r)){
        return;
    }
    if (Get(it[x], l) <= Get(val, l) && Get(it[x], r) <= Get(val, r)){
        it[x] = val;
        return;
    }
    if (Get(it[x], l) >= Get(val, l) && Get(it[x], mid) >= Get(val, mid)){
        update(2 * x + 1, mid + 1, r, u, v, val);
        return;
    }
    if (Get(it[x], l) <= Get(val, l) && Get(it[x], mid) <= Get(val, mid)){
        update(2 * x + 1, mid + 1, r, u, v, it[x]);
        it[x] = val;
        return;
    }
    if (Get(it[x], mid + 1) >= Get(val, mid + 1) && Get(it[x], r) >= Get(val, r)){
        update(2 * x, l, mid, u, v, val);
        return;
    }
    if (Get(it[x], mid + 1) <= Get(val, mid + 1) && Get(it[x], r) <= Get(val, r)){
        update(2 * x, l, mid, u, v, it[x]);
        it[x] = val;
        return;
    }
    }
    update(2 * x, l, mid, u, v, val);
    update(2 * x + 1, mid + 1, r, u, v, val);
}
 
map<long long, long long> M;
long long pos[MAXN];
 
void trau()
{
    f[0] = 0;
    FORE(i, 1, n) FORE(j, 0, i - 1) if (f[j] >= w[j] * abs(x[i] - x[j]))
            f[i] = max(f[i], f[j] - w[j] * abs(x[i] - x[j]) + e[i]);
    cout << f[n] << endl;
    //FORE(i, 1, n) cout << f[i]<<" ";cout<<endl;
    memset(f, 0, sizeof(f));
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("VOMARIO.inp", "r", stdin);
    freopen("VOMARIO.out", "w", stdout);
    #endif //YEULAPTRINH.PW
    cin >> n;
    FORE(i, 1, n){
        cin >> x[i] >> w[i] >> e[i];
        a[i] = x[i];
    }
    //trau();
    sort(a, a + n + 1);
 
    FORE(i, 0, n) b[i] = lower_bound(a, a + n + 1, x[i]) - a;
    FORE(i, 0, n) v[b[i]] = x[i], M[x[i]] = b[i];
    FORE(i, 0, n) pos[i] = M[a[i]];
    int top = *max_element(b, b + n + 1);
    FORE(i, 1, MAXN * 4 - 1) it[i].a = 0, it[i].b = 0;
    update(1, 0, top, 0, top, (line){0, 0});
    //FORE(i, 1, n + 1) cout << b[i] <<" "<<v[b[i]]<<endl;
    //FORE(i, 1, n + 1) cout<<a[i]<<" ";cout<<endl;
    //b[0] = b[n + 1];
/*
    update(1, 0, top, 0, 2, (line){-1, -1});
    update(1, 0, top, 0, 0, (line){1, 9});
    update(1, 0, top, 5, 5, (line){-4, 26});
    update(1, 0, top, 5, 5, (line){4, -6});
    cout << top << endl;
    cout << query(1, 0, top, 2)<<"wtf"<<endl;
    */
    //FORE(i, 0, n) cout << a[i]<<" ";cout<<endl;
    //FORE(i, 0, n) cout << b[i]<<" ";cout<<endl;
    long long ans = 0;
    FORE(i, 1, n){
        f[i] = query(1, 0, top, b[i]) + e[i];
        ans = max(ans, f[i]);
        long long l, r;
        if (w[i] == 0) r = top, l = 0;
        else{
            //if (i == 2) cout << (x[i] + f[i] / w[i])<<"wtf"<<endl;
            r = upper_bound(a, a + n + 1, x[i] + f[i] / w[i]) - a - 1;
            //cout << x[i] + f[i] / w[i]<<"???"<<r<<"<<<<<"<<b[r]<<endl;
            r = pos[r];
            l = lower_bound(a, a + n + 1, x[i] - f[i] / w[i]) - a;
            l = pos[l];
 
            //cout <<l<<" "<<r<<endl;
        }
        long long mid = b[i];
        update(1, 0, top, mid, r, (line){-w[i], f[i] + w[i] * x[i]});
        update(1, 0, top, l, mid, (line){w[i],  f[i] - w[i] * x[i]});
        //cout<<i<<"=+"<<b[i]<<"??"<<f[i]<<endl;
        //cout << mid <<" "<<r<<"line"<<-w[i]<<" "<<f[i] + w[i] * x[i]<<endl;
        //cout << l <<" "<<mid<<"line"<<w[i]<<" "<<f[i] - w[i] * x[i]<<endl;
    }
    cout << ans;
 
    return 0;
}