Submission #363469

#	Time	Username	Problem	Language	Result	Execution time	Memory
363469		cute_hater	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	848 ms	27740 KiB

foehn_phenomena

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <climits>
#include <stack>

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")*/

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << "No"; return;}
#define yes {cout << "Yes"; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if(0) cerr

const int N = 2e5 + 7;

int t[2][4 * N], add[2][4 * N], a[N], w[N];

void build(int v, int l, int r) {
    if (l == r) {
        t[0][v] = a[l];
        t[1][v] = w[l];
        return;
    }
    int m = l + r >> 1;
    build(2 * v + 1, l, m);
    build(2 * v + 2, m + 1, r);
}

void push(int v, int l, int r) {
    if (l != r) {
        loop(i, 2) {
            add[i][2 * v + 1] += add[i][v];
            add[i][2 * v + 2] += add[i][v];
        }
    }
    else {
        loop(i, 2) {
            t[i][v] += add[i][v];
        }
    }
    add[0][v] = add[1][v] = 0;
}

void change(int v, int l, int r, int L, int R, int val, int f) {
    push(v, l, r);
    if (l > R || r < L)
        return;
    if (l >= L && r <= R) {
        add[f][v] += val;
        push(v, l, r);
        return;
    }
    int m = l + r >> 1;
    change(2 * v + 1, l, m, L, R, val, f);
    change(2 * v + 2, m + 1, r, L, R, val, f);
}

int ask(int v, int l, int r, int pos) {
    push(v, l, r);
    if (l == r)
        return v;
    int m = l + r >> 1;
    if (pos <= m)
        return ask(2 * v + 1, l, m, pos);
    else
        return ask(2 * v + 2, m + 1, r, pos);
}

void solve() {
    int n, q, u, d;
    cin >> n >> q >> u >> d;
    ++n;
    loop(i, n) {
        cin >> a[i];
        if (i) {
            w[i] = w[i - 1];
            if (a[i] > a[i - 1])
                w[i] -= (a[i] - a[i - 1]) * u;
            else
                w[i] += (a[i - 1] - a[i]) * d;
        }
    }
    build(0, 0, n);
    loop(i, q) {
        int l, r, x;
        cin >> l >> r >> x;
        int wasl = t[0][ask(0, 0, n, l)], wasr = t[0][ask(0, 0, n, r)];
        change(0, 0, n, l, r, x, 0);
        int curl = t[0][ask(0, 0, n, l)], curr = t[0][ask(0, 0, n, r)];
        int L = t[0][ask(0, 0, n, l - 1)], R = t[0][ask(0, 0, n, r + 1)];
        change(0, 0, n, l, n, (wasl - L) * (wasl > L ? u : d) + (L - curl) * (curl > L ? u : d), 1);
        change(0, 0, n, r + 1, n, (R - wasr) * (R > wasr ? u : d) + (curr - R) * (R > curr ? u : d), 1);
        cout << t[1][ask(0, 0, n, n - 1)] << "\n";
    }
}

signed main() {
    //freopen("dream.in", "r", stdin);
    //freopen("dream.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'void build(ll, ll, ll)':
foehn_phenomena.cpp:61:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int m = l + r >> 1;
      |             ~~^~~
foehn_phenomena.cpp: In function 'void change(ll, ll, ll, ll, ll, ll, ll)':
foehn_phenomena.cpp:90:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |     int m = l + r >> 1;
      |             ~~^~~
foehn_phenomena.cpp: In function 'll ask(ll, ll, ll, ll)':
foehn_phenomena.cpp:99:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     int m = l + r >> 1;
      |             ~~^~~

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