제출 #541595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541595		Olympia	평균 (COCI14_prosjek)	C++17	50 / 50	1 ms	348 KiB

prosjek

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <limits.h>

using namespace std;

class Node {
public:
    int64_t mn = 0;
    int64_t cnt = 1;
    bool okay = true;
};

Node merge (Node x, Node y) {
    if (!x.okay) return y;
    if (!y.okay) return x;
    Node ans;
    if (x.mn == y.mn) {
        ans.mn = x.mn;
        ans.cnt = x.cnt + y.cnt;
    } else if (x.mn < y.mn){
        ans = x;
    } else if (y.mn < x.mn) {
        ans = y;
    }
    return ans;
}

void update(Node &x, int64_t val) {
    x.mn += val;
}

Node INF;

struct segmentTree {
    vector<Node> vec;
    vector<int64_t> addLater;

    void push(int v) {
        addLater[2 * v + 1] += addLater[v];
        addLater[2 * v] += addLater[v];
        vec[2 * v + 1].mn += addLater[v];
        vec[2 * v].mn += addLater[v];
        addLater[v] = 0;
    }

    void upd(int dum, int tl, int tr, int l, int r, int64_t val) {
        if (tr < l || tl > r) {
            return;
        }
        if (tl >= l && tr <= r) {
            addLater[dum] += val;
            update(vec[dum], val);
            return;
        }
        push(dum);
        int mid = (tl + tr) >> 1;
        upd(2 * dum, tl, mid, l, r, val);
        upd(2 * dum + 1, mid + 1, tr, l, r, val);
        vec[dum] = merge(vec[2 * dum], vec[2 * dum + 1]);
    }

    void upd(int l, int r, int val) {
        upd(1, 0, (int) vec.size() / 2 - 1, l, r, val);
    }

    void init (int dum, int tl, int tr) {
        if (tl == tr) {
            vec[dum].mn = 0;
            vec[dum].cnt = 1;
            return;
        }
        int mid = (tl + tr) >> 1;
        init(2 * dum, tl, mid);
        init(2 * dum + 1, mid + 1, tr);
        vec[dum] = merge(vec[2 * dum], vec[2 * dum + 1]);
    }

    Node get(int dum, int tl, int tr, int &l, int &r) {
        if (tl > r || tr < l) {
            return INF;
        }
        if (tl >= l && tr <= r) {
            //cout << tl << " " << tr <<  " " << vec[dum].cnt << '\n';
            return vec[dum];
        }
        push(dum);
        int tm = (tl + tr) >> 1;
        return merge(get(dum * 2, tl, tm, l, r), get(dum * 2 + 1, tm + 1, tr, l, r));
    }

    Node get(int l, int r) {
        return get(1, 0, (int) vec.size() / 2 - 1, l, r);
    }

    vector<int> arr;

    void resz(int n) {
        //INF.okay = false;
        int sz = ((1 << (int) ceil(log2(n))));
        vec.assign(sz * 2, INF);
        addLater.resize(sz * 2);
        arr.resize(sz);
        INF.okay = false;
        init(1, 0, (int)vec.size()/2 - 1);
    }

};
const int MAX = 1e6 + 10;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector<int64_t> arr(N);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    cout << arr[0] << ' ';
    for (int i = 1; i < N; i++) {
        cout << (i + 1) * arr[i] - i * arr[i - 1] << " ";
    }
}

• Subtask 1: 50 / 50