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 
#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<<" "< 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 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<> 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] <<" "<