Submission #1255289

---

Source Code Expand

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

class SegmentTree
{
private:
    int n;
    vector<long long> data;
    vector<long long> mulDelay;
    vector<long long> addDelay;
    void updateTree(int a, int b, int k, int l, int r, long long mulNum, long long addNum){
        if(a <= l && r <= b){
            data[k] *= mulNum;
            data[k] += addNum * (r - l + 1);
            mulDelay[k] *= mulNum;
            addDelay[k] *= mulNum;
            addDelay[k] += addNum;
        }
        else if(a <= r && l <= b){
            for(int i=0; i<2; ++i){
                data[k*2+1+i] *= mulDelay[k];
                data[k*2+1+i] += addDelay[k] * (r - l + 1) / 2;
                mulDelay[k*2+1+i] *= mulDelay[k];
                addDelay[k*2+1+i] *= mulDelay[k];
                addDelay[k*2+1+i] += addDelay[k];
            }
            mulDelay[k] = 1;
            addDelay[k] = 0;
            updateTree(a, b, k*2+1, l, (l+r)/2, mulNum, addNum);
            updateTree(a, b, k*2+2, (l+r+1)/2, r, mulNum, addNum);
            data[k] = data[k*2+1] + data[k*2+2];
        }
    }
    long long getValue(int a, int b, int k, int l, int r){
        long long ret = 0;
        if(a <= l && r <= b){
            return data[k];
        }else if(a <= r && l <= b){
            for(int i=0; i<2; ++i){
                data[k*2+1+i] *= mulDelay[k];
                data[k*2+1+i] += addDelay[k] * (r - l + 1) / 2;
                mulDelay[k*2+1+i] *= mulDelay[k];
                addDelay[k*2+1+i] *= mulDelay[k];
                addDelay[k*2+1+i] += addDelay[k];
            }
            mulDelay[k] = 1;
            addDelay[k] = 0;
            ret += getValue(a, b, k*2+1, l, (l+r)/2);
            ret += getValue(a, b, k*2+2, (l+r+1)/2, r);
        }
        return ret;
    }
public:
    SegmentTree(int n0){
        n = 1;
        while(n < n0)
            n *= 2;
        data.assign(2*n-1, 0);
        mulDelay.assign(2*n-1, 1);
        addDelay.assign(2*n-1, 0);
    }
    void set(int a, int b, long long x){ // 区間[a,b]の要素をxにする
        updateTree(a, b, 0, 0, n-1, 0, x);
    }
    void add(int a, int b, long long x){ // 区間[a,b]の要素にxを加算
        updateTree(a, b, 0, 0, n-1, 1, x);
    }
    void mul(int a, int b, long long x){ // 区間[a,b]の要素にxを乗算
        updateTree(a, b, 0, 0, n-1, x, 0);
    }
    long long get(int a, int b){         // 区間[a,b]の総和を返す
        return getValue(a, b, 0, 0, n-1);
    }
};

int main()
{
    int n, q;
    cin >> n >> q;

    SegmentTree st(n);
    while(--q >= 0){
        int a;
        long long b;
        cin >> a >> b;
        -- a;

        int left = 0;
        int right = a;
        while(left < right){
            int x = (left + right + 1) / 2;
            int w = a - x + 1;
            long long h = st.get(x-1, x-1);
            long long add = h * w - st.get(x, a);
            if(b <= add)
                left = x;
            else
                right = x - 1;
        }

        int x = left;
        int w = a - x + 1;
        b += st.get(x, a);
        st.set(x, a, b / w);
        if(b % w != 0)
            st.add(x, x + b % w - 1, 1);
    }

    for(int i=0; i<n; ++i)
        cout << st.get(i, i) << endl;

    return 0;
}

Submission Info

Judge Result