fork download

copy

#include <cstdio>
#include <algorithm>
#include <cassert>
#include <tuple>
#include <vector>
using namespace std;
 
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
 
const int N = 100500;
const int K = 230;
 
typedef long long llong;
 
int D[N];
int A[N];
 
llong PS[N];
int st[N];
 
bool was[N];
vector<int> E[N];
 
int n, k;
 
struct block {
    int len = 0;
    llong X[K] = {0};
    llong dA[K] = {0}; // Subject to further optimization
    llong glob = 0;
    llong max_req = -(llong)1e18;
    llong max_X = -(llong)1e18;
 
    void add_global(llong d) {
        glob += d;
    }
 
    inline llong get_max_req() const {
        return max_req;
    }
 
    inline llong get_max_X() const {
        return max_X + glob;
    }
 
    void recalc() {
        assert(glob == 0);
        max_req = -(llong)1e18;
        for (int i = 0; i < len; i++) {
            llong got = i ? dA[i - 1] : 0;
            if (got > k)
                break;
            max_req = max(max_req, X[i] + k - got);
        }
        max_X = *max_element(X, X + len);
    }
 
    void flush() {
        for (int i = 0; i < len; i++) {
            X[i] += glob;
            dA[i] += glob;
        }
        max_X += glob;
        glob = 0;
    }
 
    void add_suff(int x, llong d) {
        flush();
        for (int i = x; i < len; i++) {
            X[i] += d;
            dA[i] += d;
        }
        recalc();
    }
 
    // ans, mx
    pair<int, llong> get(int l, llong prev_mx = -1e18) const {
        llong mx = prev_mx;
        if (l != -1)
            mx = X[l] + glob;
        int ans = 0;
        for (int i = l + 1; i < len; i++) {
            llong got_prev = (i ? dA[i - 1] : -(llong)1e18) + glob;
            llong got = dA[i] + glob;
            if (got_prev > k)
                break;
            if (X[i] + glob + k - got >= mx) {
                ans = max(ans, i - l);
            }
            mx = max(mx, X[i] + glob);
        }
        return make_pair(ans, mx);
    }
} B[N / K + 2];
 
int blocks;
 
void add_suff(int l, llong d) {
    int id = l / K;
    B[id].add_suff(l - id * K, d);
    while (++id < blocks) {
        B[id].add_global(d);
    }
}
 
int ans = 1;
 
void process(int l) {
    int ans;
    llong mx;
    int id = l / K;
    tie(ans, mx) = B[id].get(l - id * K);
    ++ans;
    int good_id = -1;
    llong good_mx = -42;
    int prev_good_id = -1;
    llong prev_good_mx = -42;
    while (++id < blocks) {
        if (B[id - 1].dA[K - 1] + B[id - 1].glob > k)
            break;
        if (B[id].get_max_req() >= mx) {
            prev_good_id = good_id;
            prev_good_mx = good_mx;
            good_id = id;
            good_mx = mx;
        }
        mx = max(mx, B[id].get_max_X());
    }
    if (good_id != -1) {
        if ((good_id + 1) * K - l <= ::ans)
            return;
        int ans2;
        tie(ans2, ignore) = B[good_id].get(-1, good_mx);
        if (ans2 == 0) {
            if (prev_good_id != -1) {
                if ((prev_good_id + 1) * K - l <= ::ans)
                    return;
                tie(ans2, ignore) = B[prev_good_id].get(-1, prev_good_mx);
                assert(ans2 != -1);
                ans = ans2 + prev_good_id * K - l;
            }
        } else {
            ans = ans2 + good_id * K - l;
        }
    }
    //eprintf("l = %d -> ans = %d\n", l, ans);
    ::ans = max(::ans, ans);
}
 
void DFS(int x, int p = -1) {
    was[x] = true;
    if (p != -1)
        add_suff(p - 1, PS[x] - PS[p]);
    process(x);
    for (int y : E[x]) {
        DFS(y, x);
    }
    if (p != -1)
        add_suff(p - 1, PS[p] - PS[x]);
}
 
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d", &D[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }
    for (int i = 1; i < n; i++) {
        PS[i] = PS[i - 1] + A[i - 1] - D[i - 1];
    }
    int pt = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (pt > 0 && PS[st[pt - 1]] >= PS[i])
            --pt;
        if (pt)
            E[st[pt - 1]].push_back(i);
        st[pt++] = i;
    }
    llong curX = 0;
    for (int i = 1; i < n; i++)
        curX = B[i / K].X[i % K] = curX + A[i] - D[i - 1];
    blocks = (n + K - 1) / K;
    for (int id = 0; id < blocks; id++) {
        B[id].len = min(K, n - id * K);
        B[id].recalc();
    }
    for (int i = 0; i < n; i++) {
        reverse(E[i].begin(), E[i].end());
    }
    for (int i = n - 1; i >= 0; i--) {
        if (!was[i])
            DFS(i);
    }
    printf("%d\n", ans);
}
 

In file included from /usr/include/c++/5/tuple:35:0,
                 from prog.cpp:4:
/usr/include/c++/5/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support is currently experimental, and must be enabled with the -std=c++11 or -std=gnu++11 compiler options.
 #error This file requires compiler and library support for the \
  ^
prog.cpp:27:15: warning: non-static data member initializers only available with -std=c++11 or -std=gnu++11
     int len = 0;
               ^
prog.cpp:28:20: warning: non-static data member initializers only available with -std=c++11 or -std=gnu++11
     llong X[K] = {0};
                    ^
prog.cpp:29:21: warning: non-static data member initializers only available with -std=c++11 or -std=gnu++11
     llong dA[K] = {0}; // Subject to further optimization
                     ^
prog.cpp:30:18: warning: non-static data member initializers only available with -std=c++11 or -std=gnu++11
     llong glob = 0;
                  ^
prog.cpp:31:29: warning: non-static data member initializers only available with -std=c++11 or -std=gnu++11
     llong max_req = -(llong)1e18;
                             ^
prog.cpp:32:27: warning: non-static data member initializers only available with -std=c++11 or -std=gnu++11
     llong max_X = -(llong)1e18;
                           ^
prog.cpp:28:20: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
     llong X[K] = {0};
                    ^
prog.cpp:29:21: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
     llong dA[K] = {0}; // Subject to further optimization
                     ^
prog.cpp: In function 'void process(int)':
prog.cpp:112:16: error: 'tie' was not declared in this scope
     tie(ans, mx) = B[id].get(l - id * K);
                ^
prog.cpp:133:19: error: 'ignore' was not declared in this scope
         tie(ans2, ignore) = B[good_id].get(-1, good_mx);
                   ^
prog.cpp: In function 'void DFS(int, int)':
prog.cpp:155:18: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
     for (int y : E[x]) {
                  ^

Standard output is empty