제출 #1116116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1116116		staszic_ojuz	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	0 / 100	1064 ms	12984 KiB

foehn_phenomena

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <unordered_map>

using namespace std;

typedef long long ll;


class drzewo {
    public:
    ll size;
    vector<ll> pkt;
    ll s, t;
    ll rs;
    drzewo(vector<ll> &ls, ll S, ll T) {
        size = pow(2, ceil(log2(ls.size())));
        rs = ls.size();
        //cout << rs << endl;
        pkt.resize(size * 2);
        s = S;
        t = T;
        fill(pkt.begin(), pkt.end(), 0);
        for(u_int i  = 0; i < ls.size(); i++) {
            pkt[size + i] = ls[i];
        }
        reload();
    }

    void reload() {
        for(int i = size - 1; i > size/2; i--) {
            if(pkt[2*i] >= pkt[2*i + 1]) {
                pkt[i] = (pkt[2*i] - pkt[2*i + 1]) * t;
            } else {
                pkt[i] = -1 * (pkt[2*i + 1] - pkt[2*i]) * s;
            }
        }
        for(int i = size/2 - 1; i > 0; i--) {
            pkt[i] = pkt[2*i + 1] + pkt[2*i];
        }
    }

    void zmienPrzedz(ll l, ll p, ll x) {
        l = 2*l-1, p = 2*p;
        //cout << l << " " << p << " " << rs << endl;
        if(p >= rs) {
            p-=1;
        }
        //cout << l << " " << p << endl;
        for(int i = l; i <= p; i++) {
            pkt[size + i] += x;
        }
        l+= size; p+=size;
        l/=2, p/=2;
        //cout << l << " w1 " << p << endl;
        for(int i = l; i <= p; i++) {
            if(pkt[2*i] >= pkt[2*i + 1]) {
                pkt[i] = (pkt[2*i] - pkt[2*i + 1]) * t;
            } else {
                pkt[i] = -1 * (pkt[2*i + 1] - pkt[2*i]) * s;
            }
        }
        l/=2, p/=2;
        //cout << l << " " << p << endl;
        while(l > 0 || p > 0) {
            for(int i = l; i <= p; i++) {
                pkt[i] = pkt[2*i] + pkt[2*i + 1];
                ////cout << i << " " << pkt[2*i + 1] << '\n';
            }

        //cout << l << " w3 " << p << endl;
            l/=2, p/=2;
        }
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n, q, s, t; cin >> n >> q >> s >> t;
    vector<ll> c;
    for(int i = 0; i < n + 1; i++) {
        ll a; cin >> a;
        c.push_back(a);
        if(i > 0 && i < n) {
            c.push_back(a);
        }
    }
    drzewo tree = drzewo(c, s, t);
    // for(int i = 0; i < tree.size * 2; i++) {
    //     //cout << tree.pkt[i] << " ";
    // }
    //cout << tree.size << "\n";
    for(int i = 0; i < q; i++) {
        ll a, b, x;
        cin >> a >> b >> x;
        //cout << a << " " <<b << " " << x << endl;
        tree.zmienPrzedz(a, b, x);
        cout << tree.pkt[1] << '\n';
        //for(int i = 0; i < tree.size * 2; i++) {
        //cout << tree.pkt[i] << " ";
        //}
    //cout << endl;
    }

    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 10
• Subtask 3: 0 / 60