oj.uz

답안 #916539

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916539 2024-01-26T05:15:27 Z viwlesxq Foehn Phenomena (JOI17_foehn_phenomena) C++17
100 / 100
 859 ms 36672 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
    return a > b && (a = b) == b;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
    return a < b && (a = b) == b;
}
const int inf = 1e9 + 7;
const int INF = 1e18 + 7;
const int mod = 1e9 + 7;

struct segtree {
    int n;
    vector<int> t, mdf;
    segtree(int n) {
        this -> n = n;
        t.assign(4 * n + 4, 0);
        mdf.assign(4 * n + 4, 0);
    }
    void push(int v, int tl, int tr) {
        t[v] += mdf[v] * (tr - tl + 1);
        if (tl != tr) {
            mdf[2 * v] += mdf[v];
            mdf[2 * v + 1] += mdf[v];
        }
        mdf[v] = 0;
    }
    void upd(int v, int tl, int tr, int l, int r, int delta) {
        if (mdf[v]) push(v, tl, tr);
        if (tl > r || tr < l) return;
        if (tl >= l && tr <= r) {
            mdf[v] += delta;
            push(v, tl, tr);
            return;
        }
        int tm = (tl + tr) / 2;
        upd(2 * v, tl, tm, l, r, delta);
        upd(2 * v + 1, tm + 1, tr, l, r, delta);
        t[v] = t[2 * v] + t[2 * v + 1];
    } void upd(int l, int r, int delta) {
        upd(1, 1, n, l, r, delta);
    }
    int get(int v, int tl, int tr, int i) {
        if (mdf[v]) push(v, tl, tr);
        if (tl == tr) return t[v];
        int tm = (tl + tr) / 2;
        if (tm >= i) return get(2 * v, tl, tm, i);
        return get(2 * v + 1, tm + 1, tr, i);
    } int get(int i) {
        if (i < 1) return 0ll;
        return get(1, 1, n, i);
    }
};

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q, S, T;
    cin >> n >> q >> S >> T;
    int a[n + 1];
    for (int i = 0; i <= n; ++i) cin >> a[i];
    segtree t(n), h(n);
    int temp = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] < a[i - 1]) temp += (a[i - 1] - a[i]) * T;
        else temp -= (a[i] - a[i - 1]) * S;
        t.upd(i, i, temp);
        h.upd(i, i, a[i]);
    }
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        h.upd(l, r, x);
        int a = h.get(l - 1), b = h.get(l), c = t.get(l - 1), d = t.get(l);
        if (a < b) t.upd(l, r, c + (a - b) * S - d);
        else t.upd(l, r, c + (a - b) * T - d);
        if (r < n) {
            a = h.get(r), b = h.get(r + 1), c = t.get(r), d = t.get(r + 1);
            if (a < b) t.upd(r + 1, n, c + (a - b) * S - d);
            else t.upd(r + 1, n, c + (a - b) * T - d);
        }
        cout << t.get(n) << '\n';
    }
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 600 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 4 ms 772 KB Output is correct
8 Correct 5 ms 604 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 4 ms 604 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 3 ms 604 KB Output is correct
15 Correct 4 ms 600 KB Output is correct
16 Correct 3 ms 604 KB Output is correct
17 Correct 2 ms 856 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 751 ms 33840 KB Output is correct
2 Correct 847 ms 35156 KB Output is correct
3 Correct 734 ms 35124 KB Output is correct
4 Correct 791 ms 34488 KB Output is correct
5 Correct 784 ms 35824 KB Output is correct
6 Correct 330 ms 34640 KB Output is correct
7 Correct 331 ms 34640 KB Output is correct
8 Correct 608 ms 35528 KB Output is correct
9 Correct 662 ms 36200 KB Output is correct
10 Correct 665 ms 34396 KB Output is correct
11 Correct 324 ms 34560 KB Output is correct
12 Correct 318 ms 35256 KB Output is correct
13 Correct 315 ms 35360 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 600 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 4 ms 772 KB Output is correct
8 Correct 5 ms 604 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 4 ms 604 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 3 ms 604 KB Output is correct
15 Correct 4 ms 600 KB Output is correct
16 Correct 3 ms 604 KB Output is correct
17 Correct 2 ms 856 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 751 ms 33840 KB Output is correct
23 Correct 847 ms 35156 KB Output is correct
24 Correct 734 ms 35124 KB Output is correct
25 Correct 791 ms 34488 KB Output is correct
26 Correct 784 ms 35824 KB Output is correct
27 Correct 330 ms 34640 KB Output is correct
28 Correct 331 ms 34640 KB Output is correct
29 Correct 608 ms 35528 KB Output is correct
30 Correct 662 ms 36200 KB Output is correct
31 Correct 665 ms 34396 KB Output is correct
32 Correct 324 ms 34560 KB Output is correct
33 Correct 318 ms 35256 KB Output is correct
34 Correct 315 ms 35360 KB Output is correct
35 Correct 783 ms 34244 KB Output is correct
36 Correct 764 ms 35428 KB Output is correct
37 Correct 765 ms 36364 KB Output is correct
38 Correct 855 ms 35964 KB Output is correct
39 Correct 817 ms 35912 KB Output is correct
40 Correct 859 ms 35904 KB Output is correct
41 Correct 778 ms 35908 KB Output is correct
42 Correct 856 ms 36104 KB Output is correct
43 Correct 782 ms 35220 KB Output is correct
44 Correct 803 ms 35664 KB Output is correct
45 Correct 752 ms 35668 KB Output is correct
46 Correct 745 ms 36672 KB Output is correct
47 Correct 332 ms 35160 KB Output is correct
48 Correct 346 ms 35320 KB Output is correct
49 Correct 829 ms 34236 KB Output is correct
50 Correct 378 ms 35152 KB Output is correct
51 Correct 319 ms 35412 KB Output is correct
52 Correct 408 ms 35428 KB Output is correct