Submission #518932

#	Time	Username	Problem	Language	Result	Execution time	Memory
518932		Lam_lai_cuoc_doi	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	400 ms	17812 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 2e5 + 5;

struct SegmentTree
{
    int n;
    ll st[N * 4];
    SegmentTree()
    {
        memset(st, 0, sizeof st);
    }

    void Push(int id)
    {
        if (st[id])
        {
            st[id << 1] += st[id];
            st[id << 1 | 1] += st[id];
            st[id] = 0;
        }
    }

    void Build(int id, int l, int r, ll a[N])
    {
        if (l == r)
        {
            st[id] = a[l];
            return;
        }

        Build(id << 1, l, (l + r) / 2, a);
        Build(id << 1 | 1, (l + r) / 2 + 1, r, a);
    }

    void Build(ll a[N])
    {
        Build(1, 1, n, a);
    }

    void Update(int id, int l, int r, const int &a, const int &b, const ll &v)
    {
        if (l > b || r < a)
            return;
        if (l >= a && r <= b)
        {
            st[id] += v;
            return;
        }
        Push(id);

        Update(id << 1, l, (l + r) / 2, a, b, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, a, b, v);
    }

    void Update(int l, int r, ll v)
    {
        Update(1, 1, n, l, r, v);
    }

    ll Get(int x)
    {
        int l = 1, r = n, id = 1;

        while (1)
        {
            if (l == r)
                break;

            Push(id);

            if ((l + r) / 2 >= x)
            {
                id = id << 1;
                r = (l + r) / 2;
            }
            else
            {
                id = id << 1 | 1;
                l = (l + r) / 2 + 1;
            }
        }

        return st[id];
    }
} f;

int n, q;
ll s, t, a[N], ans;

void Read()
{
    cin >> n >> q >> s >> t;

    for (int i = 0; i <= n; ++i)
        cin >> a[i];
}

void Remove(int l, int r)
{
    if (r > n)
        return;

    ll u = l == 0 ? 0 : f.Get(l),
       v = f.Get(r);

    if (u < v)
        ans += (v - u) * s;
    else
        ans -= (u - v) * t;
}

void Add(int l, int r)
{
    if (r > n)
        return;

    ll u = l == 0 ? 0 : f.Get(l),
       v = f.Get(r);

    // cerr << l << " " << r << ": " << u << " " << v << "\n";

    if (u < v)
        ans -= (v - u) * s;
    else
        ans += (u - v) * t;
}

void Solve()
{
    f.n = n;
    f.Build(a);

    for (int i = 1; i <= n; ++i)
    {
        Add(i - 1, i);

        // cout << i << ": " << ans << "\n";
    }

    while (q--)
    {
        int l, r, x;
        cin >> l >> r >> x;

        Remove(l - 1, l);
        Remove(r, r + 1);

        f.Update(l, r, x);

        Add(l - 1, l);
        Add(r, r + 1);

        cout << ans << '\n';
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("tests.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        // cout << "Case " << _ << ": ";
        Read();
        Solve();
    }
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

/*
 */

Compilation message (stderr)

foehn_phenomena.cpp: In function 'void read(T&)':
foehn_phenomena.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^
foehn_phenomena.cpp: In function 'int32_t main()':
foehn_phenomena.cpp:182:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:183:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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