Submission #783805

#	Time	Username	Problem	Language	Result	Execution time	Memory
783805		makanhulia	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	546 ms	11416 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int, int>
#define piss pair<int, pii>
#define fr first
#define sc second
#define all(x) x.begin(), x.end()
using namespace std;

const int N = 2e5+5;

int n, q, s, t; 
int a[N], b[N];
int tree[N*4];

void build(int l, int r, int idx) {
    if (l == r) {
        // cout << idx << " " << l << " Lll " << endl;
        if (b[l] < 0) tree[idx] = (-s) * abs(b[l]);
        else tree[idx] = abs(b[l]) * t;
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, idx*2);
    build(mid+1, r, idx*2+1);
    tree[idx] = tree[idx*2] + tree[idx*2+1]; 
    // cout << idx << " " << tree[idx] << " " << mid << endl;
}

void update(int l, int r, int where, int idx) {
    // cerr << l << " " << r << " " << where << endl;
    if (l > where or r < where) return;
    if (l == r && r == where) {
        if (b[l] < 0) tree[idx] = (-s) * abs(b[l]);
        else tree[idx] = abs(b[l]) * t;
        return;
    }
    int mid = (l + r) / 2;
    if (where <= mid) update(l, mid, where, idx*2);
    else update(mid+1, r, where, idx*2+1);
    tree[idx] = tree[idx*2] + tree[idx*2+1]; 
}

signed main() {
    cin >> n >> q >> s >> t;
    for (int i = 0; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) b[i] = a[i-1] - a[i];
    build(1, n, 1);
    // for (int i = 1; i <= 7; i++) cout << i << ": " << tree[i] << endl;
    while(q--) {
        int x, y, z; cin >> x >> y >> z;
        b[x] -= z;
        b[y+1] += z;
        update(1, n, x, 1);
        update(1, n, y+1, 1);
        // cerr << "..." << endl;
        cout << tree[1] << endl;
    }
}

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