Submission #87887

#	Time	Username	Problem	Language	Result	Execution time	Memory
87887		tieunhi	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	227 ms	22728 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define mid (r + l)/2
#define N 2000005
#define LN 19
#define maxc 1000000007

using namespace std;

int n, numQ, S, T;
ll valUp, valDown;

struct BIT
{
    ll t[N];
    void upd(int x, ll val)
    {
        for (; x < N; x += (x & -x)) t[x] += val;
    }
    void upd(int l, int r, ll val)
    {
        upd(l, val);
        upd(r+1, -val);
    }
    ll get(int x)
    {
        ll ans = 0;
        for (; x; x -= (x & -x)) ans += t[x];
        return ans;
    }
}t;

void update(int u, int sign)
{
    if (u == n) return;
    ll val = 0;
    ll x = t.get(u);
    ll y = t.get(u+1);
    if (x < y) valUp += sign*abs(y-x);
    else valDown += sign*abs(y-x);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n >> numQ >> S >> T; n++;
    FOR(i, 1, n)
    {
        int x; cin >> x;
        t.upd(i, i, x);
    }
    FOR(i, 1, n-1) update(i, 1);
    while (numQ--)
    {
        int u, v, val; cin >> u >> v >> val; u++; v++;
        update(u-1, -1);
        update(v, -1);
        t.upd(u, v, val);
        update(u-1, 1);
        update(v, 1);
        cout <<valDown*T - valUp*S<<'\n';
    }
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'void update(int, int)':
foehn_phenomena.cpp:43:8: warning: unused variable 'val' [-Wunused-variable]
     ll val = 0;
        ^~~

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