Submission #731146

#	Time	Username	Problem	Language	Result	Execution time	Memory
731146		sleepntsheep	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	205 ms	13132 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;

template <class T>
struct BIT
{
    int n; T *a;
    BIT(int m) : n(m), a(new T[m]) {}
    ~BIT() { delete []a; }
    void inc(int p, T x) { for (; p < n; p += p&-p) a[p] += x; }
    T qry(int p, T z = 0) { for (;p; p-=p&-p) z+=a[p]; return z;}
};

using ll = long long;
#define N 402005
ll n, q, s, t;
BIT<ll> f(N), g(N);

int main()
{
    scanf("%lld%lld%lld%lld", &n, &q, &s, &t);
    for (ll i = 0, x; i <= n; i++) 
        scanf("%lld", &x), f.inc(i+1, x), f.inc(i+2, -x);

    for (int i = 1; i <= n; i++)
    {
        auto d = -f.qry(i+1) + f.qry(i);
        g.inc(i+1, (d < 0 ? s : t) * d);
    }

    auto upd = [&](int p, ll x){
        ll old = 0, aft = 0;
        auto d = f.qry(p-1) - f.qry(p);
        old = (d < 0 ? s : t) * d;
        g.inc(p, -old);
        f.inc(p, x);
        d = f.qry(p-1) - f.qry(p);
        aft = (d < 0 ? s : t) * d;
        g.inc(p, aft);
    };

    for (ll l, r, x; q--;)
    {
        scanf("%lld%lld%lld", &l, &r, &x);

        upd(l+1, x);
        upd(r+2, -x);

        printf("%lld\n", g.qry(n+1));
    }

    return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%lld%lld%lld%lld", &n, &q, &s, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%lld", &x), f.inc(i+1, x), f.inc(i+2, -x);
      |         ~~~~~^~~~~~~~~~~~
foehn_phenomena.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%lld%lld%lld", &l, &r, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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