NOIP2012 开车旅行

#include <cstdio>

#include <map>

#define LOG(FMT...) // fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef map<int, int> map_t;
typedef map_t::iterator iter_t;

const int N = 100010, LOGN = 20;

int n, m, x0, ans;
ll da, db, xa = 1000000000, xb;
int h[N], s[N], x[N];
int jump[N << 1][LOGN];
ll dist_a[N << 1][LOGN], dist_b[N << 1][LOGN];
map_t mp;

ll iabs(ll x);
iter_t nearest(iter_t it1, iter_t it2, int x);
void calc_dist(int s, int x);

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &h[i]);
    mp.insert(make_pair(h[n], n));
    mp.insert(make_pair(h[n - 1], n - 1));
    jump[((n - 1) << 1) | 1][0] = n << 1;
    dist_b[((n - 1) << 1) | 1][0] = iabs(h[n] - h[n - 1]);
    for (int i = n - 2; i; --i) {
        iter_t it = mp.insert(make_pair(h[i], i)).first, prv, nxt;
        prv = it;
        if (prv == mp.begin())
            prv = mp.end();
        else
            --prv;
        nxt = it;
        ++nxt;
        int k = i << 1;
        if (nearest(prv, nxt, h[i]) == prv) {
            jump[k | 1][0] = prv->second << 1;
            LOG("%d->%d ", i, prv->second);
            dist_b[k | 1][0] = iabs(prv->first - h[i]);
            if (prv == mp.begin())
                prv = mp.end();
            else
                --prv;
        } else {
            jump[k | 1][0] = nxt->second << 1;
            LOG("%d->%d ", i, nxt->second);
            dist_b[k | 1][0] = iabs(nxt->first - h[i]);
            if (nxt != mp.end())
                ++nxt;
        }
        LOG("%d\n", prv == mp.end());
        if (nearest(prv, nxt, h[i]) == prv) {
            jump[k][0] = (prv->second << 1) | 1;
            LOG("%d\n", prv->second);
            dist_a[k][0] = iabs(prv->first - h[i]);
        } else {
            jump[k][0] = (nxt->second << 1) | 1;
            LOG("%d\n", nxt->second);
            dist_a[k][0] = iabs(nxt->first - h[i]);
        }
        LOG("FINE %d\n", i);
    }
    for (int i = n; i; --i)
        for (int k = i << 1; k <= ((i << 1) | 1); ++k)
            for (int j = 1; j < LOGN; ++j) {
                jump[k][j] = jump[jump[k][j - 1]][j - 1];
                dist_a[k][j] = dist_a[k][j - 1] + dist_a[jump[k][j - 1]][j - 1];
                dist_b[k][j] = dist_b[k][j - 1] + dist_b[jump[k][j - 1]][j - 1];
            }
    scanf("%d%d", &x0, &m);
    for (int i = 1; i <= m; ++i)
        scanf("%d%d", &s[i], &x[i]);
    for (int i = 1; i <= n; ++i) {
        calc_dist(i, x0);
        if (db == 0) {
            if (xb == 0 && h[ans] < h[i]) {
                xa = da;
                ans = i;
            }
        } else if ((ll)da * xb < (ll)xa * db || ((ll)da * xb == (ll)xa * db && h[ans] < h[i])) {
            ans = i;
            xa = da;
            xb = db;
            LOG("NEW %d\n", i);
        }
    }
    LOG("%lld %lld\n", xa, xb);
    printf("%d\n", ans);
    for (int i = 1; i <= m; ++i) {
        calc_dist(s[i], x[i]);
        printf("%lld %lld\n", da, db);
    }
    return 0;
}

inline void calc_dist(int s, int x) {
    da = db = 0;
    s <<= 1;
    for (int j = LOGN - 1; ~j; --j)
        if (dist_a[s][j] + dist_b[s][j] + da + db <= x) {
            da += dist_a[s][j];
            db += dist_b[s][j];
            s = jump[s][j];
        }
}

inline ll iabs(ll x)
{ return x < 0 ? -x : x; }

inline iter_t nearest(iter_t it1, iter_t it2, int x) {
    if (it1->first == x || it1 == mp.end())
        return it2;
    if (it2->first == x || it2 == mp.end())
        return it1;
    if (iabs(it1->first - x) <= iabs(it2->first - x))
        return it1;
    return it2;
}