Submission #1258775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258775		sunit	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	369 ms	68312 KiB

foehn_phenomena

#include<bits/stdc++.h>
#define int long long
#define bl bool
#define db double 
#define fl float 
#define st string 
#define pb push_back
#define pf push_front
#define is insert
#define endl "\n"
#define pba pop_back
#define pfr pop_front
#define ub upper_bound
#define lb lower_bound 
#define fi first 
#define se second 
#define FOR(i, l, r, st) for(int i = l; i <= r; i += st)
#define FOS(i, l, r, sl) for(int i = l; i >= r; i -= sl)
#define mii map<int, int>
#define us unordered_set 
#define pii pair<int, int>
#define vt vector
using namespace std;

const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

struct SEG{
    int seg[4 * maxn], lz[4 * maxn];
    void inp() {
        memset(seg, 0, sizeof(seg));
        memset(lz, 0, sizeof(lz));
    }
    void push(int id, int l, int r) {
        if(lz[id] != 0) {
            seg[id] = seg[id] + lz[id] * (r - l + 1);
            if(l != r) {
                lz[2 * id] += lz[id];
                lz[2 * id + 1] += lz[id];
            }
            lz[id] = 0;
        }
    }
    void up(int id, int l, int r, int lr, int rr, int val) {
        push(id, l, r);
        if(lr > r || rr < l) return;
        if(lr <= l && r <= rr) {
            lz[id] += val;
            push(id, l, r);
            return;
        }
        int mid = (l + r) / 2;
        up(2 * id, l, mid, lr, rr, val);
        up(2 * id + 1, mid + 1, r, lr, rr, val);
        seg[id] = seg[2 * id] + seg[2 * id + 1];
    }
    int get(int id, int l, int r, int pos) {
        push(id, l, r);
        if(l > pos || r < pos) return 0;
        if(l == r) return seg[id];
        int mid = (l + r) / 2;
        if(pos <= mid) return get(2 * id, l, mid, pos);
        else return get(2 * id + 1, mid + 1, r, pos);
    }
} seg;

int n, q, s, t, a[maxn];

int rep(int l, int r) {
    if(l >= r) return ((l - r) * t);
    else return -((r - l) * s);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    seg.inp();
    cin >> n >> q >> s >> t;
    int res = 0;
    FOR(i, 0, n, 1) cin >> a[i];
    FOR(i, 0, n - 1, 1) res += rep(a[i], a[i + 1]);

    while(q --) {
        int l, r, val; cin >> l >> r >> val;
        int lef1 = a[l - 1] + seg.get(1, 0, n, l - 1);
        int lef2 = a[l] + seg.get(1, 0, n, l);
        res -= rep(lef1, lef2);

        if(r < n) {
            int rit1 = a[r] + seg.get(1, 0, n, r);
            int rit2 = a[r + 1] + seg.get(1, 0, n, r + 1);
            res -= rep(rit1, rit2);
        }

        seg.up(1, 0, n, l, r, val);

        lef1 = a[l - 1] + seg.get(1, 0, n, l - 1);
        lef2 = a[l] + seg.get(1, 0, n, l);
        res += rep(lef1, lef2);

        if(r < n) {
            int rit1 = a[r] + seg.get(1, 0, n, r);
            int rit2 = a[r + 1] + seg.get(1, 0, n, r + 1);
            res += rep(rit1, rit2);
        }

        cout << res << endl;
    }
}

Compilation message (stderr)

foehn_phenomena.cpp:74:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 | main() {
      | ^~~~

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