Hamako Online Judge #097 ukuku09: 001 - photography

,

solution

累積和の列をsortして潰してしゃくとり法や二分探索。$O(N \log N)$。

数列$X$に対し累積和$a$を取ると答えは$\max \{ r - l \mid a_r - a_l \ge P \}$。 添字$l$を固定したときに$a_r \ge P + a_l$であるような最大の$r$を求められればよい。 $r \lt r’$で$a_r \le a_{r’}$なら$(r, a_r)$はまったく不要であることを使って、そのようなものを除いて列$a_{r_k}$を作ればこれは単調増加列。この上で二分探索とかをすればよい。

implementation

#include <cstdio>
#include <map>
#include <numeric>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

int main() {
    // input
    int n; ll p; scanf("%d%lld", &n, &p);
    vector<ll> x(n); repeat (i, n) scanf("%lld", &x[i]);
    // solve
    vector<ll> acc(n + 1); whole(partial_sum, x, acc.begin() + 1);
    map<ll, int> left, right;
    repeat (i, n + 1) {
        if (not  left.count(acc[i])) {  left[acc[i]] = i; } else { setmin( left[acc[i]], i); }
        if (not right.count(acc[i])) { right[acc[i]] = i; } else { setmax(right[acc[i]], i); }
    }
    for (auto it = right.begin(); ; ) {
        auto next = it; ++ next;
        if (next == right.end()) break;
        ll a = it->first;
        ll b = next->first;
        if (a < b and right[a] <= right[b]) {
            right.erase(it);
            it = right.find(b);
            if (it != right.begin()) -- it;
        } else {
            it = next;
        }
    }
    int result = 0;
    auto r = right.begin();
    auto l = left.begin();
    for (; l != left.end(); ++ l) {
        while (r != right.end() and r->first - l->first < p) ++ r;
        if (r == right.end()) break;
        setmax(result, r->second - l->second);
    }
    // output
    printf("%d\n", result);
    return 0;
}