Submission #731139

#	Time	Username	Problem	Language	Result	Execution time	Memory
731139		sleepntsheep	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	0 / 100	16 ms	3628 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(T p, int x) { for (; p < n; p += p&-p) a[p] += x; }
    auto qry(int p, T z = 0) { for (;p; p-=p&-p) z+=a[p]; return z;}
    void updmax(int p, T x) { for (;p<n; p+=p&-p) a[p]=std::max(x,a[p]);}
    auto qrymax(int p, T z) { for (;p; p-=p&-p) z=std::max(z,a[p]); return z;}
};

#define N 100005
int n, q, s, t, a[N];
BIT<long long> f(N), g(N);

int main()
{
    scanf("%d%d%d%d", &n, &q, &s, &t);
    for (int i = 0; i <= n; i++) scanf("%d", a+i), f.inc(i+1, a[i]), f.inc(i+2, -a[i]);
    for (int i = 1; i <= n; i++)
    {
        auto d = -f.qry(i+1) + f.qry(i);
        if (d < 0) g.inc(i+1, s * d);
        else g.inc(i+1, t * d);
    }

#if 0
    puts("Altitude");
    for (int i = 0; i <= n; i++) printf("%lld ", f.qry(i+1)); puts("");
    puts("Temp");
    for (int i = 0; i <= n; i++) printf("%lld ", g.qry(i+1)); puts("");
#endif

    for (int l, r, x; q--;)
    {
        long long lo = 0, ro = 0, ln = 0, rn = 0;
        scanf("%d%d%d", &l, &r, &x);

        if (f.qry(l) < f.qry(l+1)) lo = s * (f.qry(l) - f.qry(l+1)); else lo = t * (f.qry(l) - f.qry(l+1));
        if (f.qry(r+1) < f.qry(r+2)) ro = s * (f.qry(r+1) - f.qry(r+2)); else ro = t * (f.qry(r+1) - f.qry(r+2));

        f.inc(l+1, x), f.inc(r+2, -x);

        if (f.qry(l) < f.qry(l+1)) ln = s * (f.qry(l) - f.qry(l+1)); else ln = t * (f.qry(l) - f.qry(l+1));
        if (f.qry(r+1) < f.qry(r+2)) rn = s * (f.qry(r+1) - f.qry(r+2)); else rn = t * (f.qry(r+1) - f.qry(r+2));

        g.inc(l+1, ln - lo);
        g.inc(r+2, rn - ro);
        printf("%lld\n", g.qry(n+1));

#if 0
        puts("Altitude");
        for (int i = 0; i <= n; i++) printf("%lld ", f.qry(i+1)); puts("");
        puts("Temp");
        for (int i = 0; i <= n; i++) printf("%lld ", g.qry(i+1)); puts("");
#endif
    }

    return 0;
}

Compilation message (stderr)

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

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