Submission #731147

#	Time	Username	Problem	Language	Result	Execution time	Memory
731147		sleepntsheep	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	200 ms	7552 KiB

foehn_phenomena

#include <stdio.h>
#include <algorithm>

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

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

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

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

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

    for (ll l, r, x; q--;)
    {
        scanf("%lld%lld%lld", &l, &r, &x);
        upd(l, x);
        upd(r+1, -x);
        printf("%lld\n", g.qry(n));
    }

    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("%d%d%d%d", &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, x), f.inc(i+1, -x);
      |         ~~~~~^~~~~~~~~~~~
foehn_phenomena.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%lld%lld%lld", &l, &r, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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