提出 #61571651

---

ソースコード 拡げる

#ifndef ATCODER // AtCoder 環境でない場合はデバッグモードを有効にする. コンパイルにすごく時間がかかる！
#define _GLIBCXX_DEBUG // out of rangeを検出してくれる。#include<bits/stdc++.h>の前に記述する必要あり
#endif
#include<bits/stdc++.h>
using namespace std;
struct IOSetup {
    IOSetup() {
        // 実行が高速化するコード
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        // 小数点以下10桁まで(四捨五入)
        cout << fixed << setprecision(10);
    }
} iosetup;
#define rep(i, n) for (long long i = 0; i < n; i++)
#define rep2(i, a, b) for (long long i = a; i < b; i++)
#define rrep(i, b, a) for (long long i = b; i > a; i--)
#define rep3(i, a, b, d) for (long long i = a; i < b; i+=d)
#define rrep3(i, b, a, d) for (long long i = b; i > a; i-=d)
#define between(x, a, b) (((a) <= (x)) && ((x) < (b)))

// Template function to print various container types
template<typename Container>
void print(const Container& a) {
    cout << "{";
    bool first = true;
    for (const auto& i : a) {
        if (!first) {
            cout << ",";
        }
        cout << i;
        first = false;
    }
    cout << "}" << endl;
}


// Template function to print 2D vector
template<typename T>
void printvec2d(const vector<vector<T>>& a) {
    size_t rows = a.size();
    for (size_t i = 0; i < rows; ++i) {
        print(a[i]);
    }
}

// Template function to print 3D vector
template<typename T>
void printvec3d(const vector<vector<vector<T>>>& a) {
    size_t depth = a.size();
    for (size_t i = 0; i < depth; ++i) {
        printvec2d(a[i]);
        cout << endl;
    }
}


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

struct LazySegmentTree {
private:
    int N;
    vector<long long> node, lazy;

public:
    LazySegmentTree(vector<long long> v) {
        int sz = (int)v.size();
        N = 1; while(N < sz) N *= 2;
        node.resize(2*N-1);
        lazy.resize(2*N-1, 0);

        for(int i=0; i<sz; i++) node[i+N-1] = v[i];
        for(int i=N-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
    }

    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }

    void add(int a, int b, long long x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = N;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else {
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }

    long long getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = N;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        long long vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        long long vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }

    long long get(int a) {
        return getsum(a, a + 1);
    }
};
// add(l, r, x) [l, r)にxを加算
// get_sum(l, r, x) [l, r)の総和を取得
// get(i) iのindexを取得

int main() {
    long long n;
    cin >> n;
    vector<long long> a(n);
    rep(i, n) cin >> a[i];
    LazySegmentTree seg(a);
    rep(i, n - 1) {
        long long gap = min(n - i - 1, seg.get(i));
        seg.add(i + 1, min(i + gap + 1, n), 1);
        seg.add(i, i + 1, -gap);
        // rep(i, n) {
        //     cout << seg.get(i) << " ";
        // }
        // cout << endl;
    }
    rep(i, n) {
        cout << seg.get(i) << " ";
    }
    return 0;

}

提出情報

ジャッジ結果