Hamako Online Judge ukuku09 contest A photography

問題概要

https://hoj.hamako-ths.ed.jp/onlinejudge/problems/766
うくさんはコンテストのために以下のような問題を考えました。
N人が横1列に並んでいます。左からi番目の人の可愛さは です。可愛さが負になることもあります。
チノちゃんは列のある連続する範囲にいる人たちを写真に収めたいです。ただし写真の中にいる人の可愛さの総和がP以上である必要があります。
このとき, 写真の中にいる人の最大の人数を出力してください。
,,

解説

区間+座標圧縮+にぶたん
問題からを考える。
累積和をキーにして、これをみたすの組のうち区間長が最大になるものを見つけたい。
式変形を行いをみる。
を昇順に並び替え順番にiを見ていくときに、欲しい累積和の最大値がこれで決まったので
この最大値以下のうちindexが最小のものを見つける。
これは累積和を座標圧縮したものをソートして最小値のseg木にのせておけば対数時間で見つけることができる。

コード

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)

struct SegTree {
	ll N;
	vector<ll> dat;
	SegTree(ll _N) {
		N = 1;
		while (N < _N)N *= 2;
		dat = vector<ll>(N * 2 - 1, INT_MAX);
	}
	void update(ll k, ll val) {
		k += N - 1;
		dat[k] = val;
		while (k) { // 根まで再帰的に上る
			k = (k - 1) / 2;
			dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]); // merge
		}
	}
	// 区間[a,b)の評価
	ll query(ll a, ll b, ll k, ll l, ll r) {
		if (r == -1)r = N;
		if (r <= a || b <= l)return INT_MAX; // 区間が被らない 
		if (a <= l&&b >= r)return dat[k]; // 値を返す
		ll v1 = query(a, b, k * 2 + 1, l, (l + r) / 2);
		ll v2 = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return min(v1, v2); //merge
	}
	inline ll query(ll a, ll b) {
		return query(a, b, 0, 0, N);
	}
};


ll N, P;
ll a[200005];
ll sum[200005];
bool f[200005];
ll ans = 0;

int main() {

	scanf("%lld %lld", &N, &P);
	vector<ll>v;
	ll b = 0;
	v.push_back(0LL);

	for (int i = 0; i < N; i++) {
		scanf("%lld", &a[i]);
		sum[i + 1] = sum[i] + a[i];
		v.push_back(sum[i + 1]);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());

	SegTree seg(v.size());

	FOR(i, 0, N + 1) f[i] = 0;

	FOR(i, 0, N + 1) {
		int x = lower_bound(v.begin(), v.end(), sum[i]) - v.begin();
		if (!f[x]) {
			f[x] = 1;
			seg.update(x, i);
		}

		int y = upper_bound(v.begin(), v.end(), sum[i] - P) - v.begin();
		int j = seg.query(0, y);
		if (j != INT_MAX)
			ans = max(ans, (ll)(i - j));
	}

	printf("%d\n", ans);
	return 0;
}