Submission #46639

#	Time	Username	Problem	Language	Result	Execution time	Memory
46639		eropsergeev	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	179 ms	7548 KiB

foehn_phenomena

#ifdef LOCKAL
    #define _GLIBCXX_DEBUG
#endif
//#ifndef LOCKAL
    #pragma GCC optimize("Ofast")
    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,mmx,avx")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("unroll-all-loops")
//#endif
#include <bits/stdc++.h>
//#define TIMUS
//#define FILENAME "journey"
#ifndef TIMUS
    #include <ext/rope>
    #include <ext/pb_ds/assoc_container.hpp>
#endif // TIMUS
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int INF = INT_MAX / 2;
const ll LINF = (ll)2e18 + 666, M = 1e9 + 7;
const ld EPS = 1e-7;

#ifndef M_PI
    const ld M_PI = acos(-1);
#endif // M_PI

using namespace std;

#ifndef TIMUS
    using namespace __gnu_cxx;
    using namespace __gnu_pbds;

    template<class K, class T>
    using ordered_map = tree<K, T, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

    template<class T>
    using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif

void run();

template<class T1, class T2>
inline bool mini(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}

template<class T1, class T2>
inline bool maxi(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}

int main()
{
    #ifndef LOCKAL
        #ifdef FILENAME
            freopen(FILENAME".in", "r", stdin);
            freopen(FILENAME".out", "w", stdout);
        #endif // FILENAME
    #endif
    #ifndef TIMUS
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif // TIMUS
    srand(time(0));
    auto start = clock();
    run();
    #ifdef LOCKAL
        //cout << endl;
        cout << "\ntime = " << (ld)(clock() - start) / CLOCKS_PER_SEC << "\n";
    #endif
    return 0;
}

//#define DEBUG
#if defined DEBUG && defined LOCKAL
    #define debugdo(x) x
#else
    #define debugdo(x)
#endif

#define debug_for(x) debug(#x": "); debugdo(for (auto &_x: x)) debug2(_x); debug("")
#define debug(x) debugdo(cout << x << endl)
#define debug2(x) debugdo(cout << x << " ")

// ---SOLUTION--- //

//#define FAST 1e9
#ifdef FAST
    char buf[(int)FAST];
    size_t p = 0;
    inline void *operator new(size_t n)
    {
        p += n;
        return buf + p - n;
    }
    inline void operator delete(void *){}
#endif

void run()
{
    int n, q, s, t;
    cin >> n >> q >> s >> t;
    vector<ll> a(n + 1);
    for (int i = 0; i <= n; i++)
        cin >> a[i];
    vector<ll> d(n + 1);
    d[0] = 0;
    for (int i = 1; i <= n; i++)
        d[i] = a[i] - a[i - 1];
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (d[i] > 0)
            ans += s * d[i];
        else
            ans += t * d[i];
    }
    while (q--)
    {
        int l, r;
        ll x;
        cin >> l >> r >> x;
        if (d[l] > 0)
            ans -= d[l] * s;
        else
            ans -= d[l] * t;
        d[l] += x;
        if (d[l] > 0)
            ans += d[l] * s;
        else
            ans += d[l] * t;
        if (r < n)
        {
            if (d[r + 1] > 0)
                ans -= d[r + 1] * s;
            else
                ans -= d[r + 1] * t;
            d[r + 1] -= x;
            if (d[r + 1] > 0)
                ans += d[r + 1] * s;
            else
                ans += d[r + 1] * t;
        }
        cout << -ans << "\n";
    }
}
/*
+1
-2
0 6 3  8
0 1 -1 0
*/

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:86:10: warning: unused variable 'start' [-Wunused-variable]
     auto start = clock();
          ^~~~~

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