Minions and Voting [CodeChef March Challenge 2018 Div1 C]

https://www.codechef.com/MARCH18A/problems/MINVOTE
N要素の配列Sがある。
「j番目がi番目に投票する ↔ (i~j番目のSの総和-S[i]-S[j])≦S[j]」のとき、各参加者が得る投票数を答えよ。

前提知識

• imos法
• 二分探索

解法

https://www.codechef.com/viewsolution/17598024

i番目の人が誰に投票するかを考えてみる。
i番目の人が投票する人は左に進んでいって間の総和がS[i]を越えるまで投票し続ける。
右も同様に、右に進んでいって間の総和がS[i]を越えるまで投票し続ける。
つまり、左右に伸ばしていった自分自身を除いた区間投票すると言える。
そのため投票する左端と右端を二分探索で探し出し、自分自身を除いた区間全てに+1する。
区間への+1はimos法を使うといい。

int N;
ll S[101010], sm[101010];
int ans[101010];
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> N; rep(i, 0, N) cin >> S[i];
    sm[0] = S[0];
    rep(i, 1, N) sm[i] = sm[i - 1] + S[i];
    rep(i, 0, N) ans[i] = 0;
 
    rep(i, 0, N) {
        if (i) { // [0,i)
            int ng = -1, ok = i - 1;
            while (ng + 1 != ok) {
                int x = (ok + ng) / 2;
 
                ll s = sm[i - 1] - sm[x];
                if (s <= S[i]) ok = x;
                else ng = x;
            }
 
            ans[ok]++;
            ans[i]--;
        }
 
        if (i < N - 1) { // (i,N)
            int ok = i + 1, ng = N;
            while (ok + 1 != ng) {
                int x = (ok + ng) / 2;
 
                ll s = sm[x - 1] - sm[i];
                if (s <= S[i]) ok = x;
                else ng = x;
            }
 
            ans[i + 1]++;
            ans[ng]--;
        }
    }
 
    rep(i, 1, N) ans[i] += ans[i - 1];
    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T;  cin >> T;
    rep(t, 0, T) solve();
}