Submission #981132

#	Time	Username	Problem	Language	Result	Execution time	Memory
981132		ShaShi	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	294 ms	23244 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define kill(x) cout << x << endl, exit(0);
#define endl "\n"

 
using namespace std;
typedef long long ll;
typedef long double ld;
 

const int MAXN = (int)1e6 + 7;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;


int n, m, q, tmp, tmp2, tmp3, tmp4, ans, k, u, v, w, flag;
int arr[MAXN], A, B, U, D;



/* Segment Tree */
#define mid ((l+r)>>1)
#define lid (id<<1)
#define rid (lid|1)


int seg[MAXN<<2], lazy[MAXN<<2];


inline void relax(int l, int r, int id) {
    if (lazy[id] == 0) return;

    seg[lid] += lazy[id]; seg[rid] += lazy[id];
    lazy[lid] += lazy[id]; lazy[rid] += lazy[id];
    lazy[id] = 0;
}


void build(int l=0, int r=n, int id=1) {
    if (l+1 == r) {
        seg[id] = arr[l];
        return;
    }

    build(l, mid, lid);
    build(mid, r, rid);

    seg[id] = seg[lid]+seg[rid];
}


void upd(int s, int t, int x, int l=0, int r=n, int id=1) {
    if (s >= t) return;
    if (s <= l && t >= r) {
        seg[id] += x;
        lazy[id] += x;
        return;
    }

    relax(l, r, id);

    if (s < mid) upd(s, t, x, l, mid, lid);
    if (t > mid) upd(s, t, x, mid, r, rid);

    seg[id] = seg[lid]+seg[rid];
}


int get(int x, int l=0, int r=n, int id=1) {
    if (l+1 == r) return seg[id];

    relax(l, r, id);

    if (x < mid) return get(x, l, mid, lid);
    return get(x, mid, r, rid);
}


/* Segment Tree */


inline void f(int u, int v, int x) {
    if (u < v) U += (v-u)*x;
    else D += (u-v)*x;
}


int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q >> A >> B; n++;

    for (int i=0; i<n; i++) {
        cin >> arr[i];
        
        if (i) f(arr[i-1], arr[i], 1);
    }

    build();

    while (q--) {
        cin >> u >> v >> w;

        f(get(u-1), get(u), -1);
        if (v != n-1) f(get(v), get(v+1), -1);

        upd(u, v+1, w);

        f(get(u-1), get(u), 1);
        if (v != n-1) f(get(v), get(v+1), 1);

        // cout << "!";
        cout << D*B-U*A << endl;
    }


    return 0;
}

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