Submission #34033

#	Time	Username	Problem	Language	Result	Execution time	Memory
34033		DoanPhuDuc	Foehn Phenomena (JOI17_foehn_phenomena)	C++98	100 / 100	256 ms	4360 KiB

foehn_phenomena

#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
#define BitCount(x) __builtin_popcount(x)

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;

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

LL ans = 0;

struct FenwickTree {
    LL fw[N];
    void Update(int l, int r, int v) {
        for (l; l <= n; l += l & -l) fw[l] += v;
        ++r;
        for (r; r <= n; r += r & -r) fw[r] -= v;
    }
    LL Query(int i) {
        LL ans = 0;
        for (i; i > 0; i -= i & -i) ans += fw[i];
        return ans;
    }
} FT;

void Change(LL v1, LL v2, int d) {
    if (v1 < v2) ans += d * (LL)s * (v1 - v2);
        else ans += d * (LL)t * (v1 - v2);
}

void Update(int l, int r, int x) {
    if (r < n) {
        LL v1 = a[r] + FT.Query(r), v2 = a[r + 1] + FT.Query(r + 1);
        Change(v1, v2, -1);
        v1 += x;
        Change(v1, v2, +1);
    }
    LL v1 = a[l - 1] + FT.Query(l - 1), v2 = a[l] + FT.Query(l);
    Change(v1, v2, -1);
    v2 += x;
    Change(v1, v2, +1);
    FT.Update(l, r, x);
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d%d%d%d", &n, &q, &s, &t);
    FOR(i, 0, n) scanf("%d", &a[i]);
    FOR(i, 1, n)
        if (a[i] > a[i - 1]) ans += (LL)s * (a[i - 1] - a[i]);
            else ans += (LL)t * (a[i - 1] - a[i]);
    while (q--) {
        int l, r, x; scanf("%d%d%d", &l, &r, &x);
        Update(l, r, x);
        printf("%lld\n", ans);
    }
    return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In member function 'void FenwickTree::Update(int, int, int)':
foehn_phenomena.cpp:25:15: warning: statement has no effect [-Wunused-value]
         for (l; l <= n; l += l & -l) fw[l] += v;
               ^
foehn_phenomena.cpp:27:15: warning: statement has no effect [-Wunused-value]
         for (r; r <= n; r += r & -r) fw[r] -= v;
               ^
foehn_phenomena.cpp: In member function 'LL FenwickTree::Query(int)':
foehn_phenomena.cpp:31:15: warning: statement has no effect [-Wunused-value]
         for (i; i > 0; i -= i & -i) ans += fw[i];
               ^
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:60:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &q, &s, &t);
                                      ^
foehn_phenomena.cpp:61:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 0, n) scanf("%d", &a[i]);
                                    ^
foehn_phenomena.cpp:66:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int l, r, x; scanf("%d%d%d", &l, &r, &x);
                                                 ^

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