Submission #679585

#	Time	Username	Problem	Language	Result	Execution time	Memory
679585		elkernos	Fish 2 (JOI22_fish2)	C++17	0 / 100	4 ms	3668 KiB

fish2

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int nax = 1 << 17;
const ll oo = 1e17;

int n;
#define lc 2 * v
#define rc 2 * v + 1
#define m (l + r) / 2
struct CMin {
    struct Node {
        pii p = {0, 1};
        int lazy = 0;
        void dod(int x)
        {
            p.first += x;
            lazy += x;
        }
    };
    Node nothing = {{nax, 0}, 0};
    friend Node operator+(const Node &l, const Node &r)
    {
        Node ret;
        ret.p = min(l.p, r.p);
        if (l.p.first == r.p.first) ret.p.second = l.p.second + r.p.second;
        return ret;
    }
    Node tree[2 * nax];
    void push(int v)
    {
        for (auto to : {lc, rc})
            tree[to].dod(tree[v].lazy);
        tree[v].lazy = 0;
    }
    void build(int v = 1, int l = 0, int r = n + 1)
    {
        if (l == r) {
            tree[v].p.second = 1;
            return;
        }
        build(lc, l, m), build(rc, m + 1, r);
        tree[v] = tree[lc] + tree[rc];
    }
    void add(int ql, int qr, int x, int v = 1, int l = 0, int r = n + 1)
    {
        if (r < ql || qr < l) return;
        if (ql <= l && r <= qr) {
            tree[v].dod(x);
            return;
        }
        push(v);
        add(ql, qr, x, lc, l, m), add(ql, qr, x, rc, m + 1, r);
        tree[v] = tree[lc] + tree[rc];
    }
    Node query(int ql, int qr, int v = 1, int l = 0, int r = n + 1)
    {
        if (r < ql || qr < l) return nothing;
        if (ql <= l && r <= qr) return tree[v];
        push(v);
        return query(ql, qr, lc, l, m) + query(ql, qr, rc, m + 1, r);
    }
} intervals;
struct Sum {
    ll s[nax];
    void update(int pos, ll dif)
    {
        for (; pos < nax; pos |= pos + 1)
            s[pos] += dif;
    }
    ll query(int pos)
    {
        ll res = 0;
        for (; pos > 0; pos &= pos - 1)
            res += s[pos - 1];
        return res;
    }
    ll query(int a, int b)
    {
        return query(b + 1) - query(a);
    }
} getsum;
struct Max {
    ll tree[2 * nax];
    void update(int pos, ll to, int v = 1, int l = 0, int r = n + 1)
    {
        if (pos < l || r < pos) return;
        if (l == r) {
            tree[v] = to;
            return;
        }
        update(pos, to, lc, l, m), update(pos, to, rc, m + 1, r);
        tree[v] = max(tree[lc], tree[rc]);
    }
    int maxPrawo(int ogr, ll od, int v = 1, int l = 0, int r = n + 1)
    {
        if (tree[v] <= od) return -1;
        if (l == r) return l;
        if (ogr <= m) return maxPrawo(ogr, od, lc, l, m);
        int ret = maxPrawo(ogr, od, rc, m + 1, r);
        return ret != -1 ? ret : maxPrawo(ogr, od, lc, l, m);
    }
    int maxLewo(int ogr, ll od, int v = 1, int l = 0, int r = n + 1)
    {
        if (tree[v] <= od) return -1;
        if (l == r) return l;
        if (m < ogr) return maxLewo(ogr, od, rc, m + 1, r);
        int ret = maxLewo(ogr, od, lc, l, m);
        return ret != -1 ? ret : maxLewo(ogr, od, rc, m + 1, r);
    }
} getmax;

namespace fastio {
static constexpr int SZ = 1 << 17;
char ibuf[SZ], obuf[SZ];
int pil = 0, pir = 0, por = 0;

struct Pre {
    char num[40000];
    constexpr Pre() : num()
    {
        for (int i = 0; i < 10000; i++) {
            int n = i;
            for (int j = 3; j >= 0; j--) {
                num[i * 4 + j] = n % 10 + '0';
                n /= 10;
            }
        }
    }
} constexpr pre;

inline void load()
{
    memcpy(ibuf, ibuf + pil, pir - pil);
    pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
    pil = 0;
}
inline void flush()
{
    fwrite(obuf, 1, por, stdout);
    por = 0;
}

inline void skip_space()
{
    if (pil + 32 > pir) load();
    while (ibuf[pil] <= ' ')
        pil++;
}

inline void rd(char &c)
{
    if (pil + 32 > pir) load();
    c = ibuf[pil++];
}
template <typename T>
inline void rd(T &x)
{
    if (pil + 32 > pir) load();
    char c;
    do
        c = ibuf[pil++];
    while (c < '-');
    [[maybe_unused]] bool minus = false;
    if constexpr (is_signed<T>::value == true) {
        if (c == '-') minus = true, c = ibuf[pil++];
    }
    x = 0;
    while (c >= '0') {
        x = x * 10 + (c & 15);
        c = ibuf[pil++];
    }
    if constexpr (is_signed<T>::value == true) {
        if (minus) x = -x;
    }
}
inline void rd() {}
template <typename Head, typename... Tail>
inline void rd(Head &head, Tail &...tail)
{
    rd(head);
    rd(tail...);
}

inline void wt(char c)
{
    if (por > SZ - 32) flush();
    obuf[por++] = c;
}
inline void wt(bool b)
{
    if (por > SZ - 32) flush();
    obuf[por++] = b ? '1' : '0';
}
template <typename T>
inline void wt(T x)
{
    if (por > SZ - 32) flush();
    if (!x) {
        obuf[por++] = '0';
        return;
    }
    if constexpr (is_signed<T>::value == true) {
        if (x < 0) obuf[por++] = '-', x = -x;
    }
    int i = 12;
    char buf[16];
    while (x >= 10000) {
        memcpy(buf + i, pre.num + (x % 10000) * 4, 4);
        x /= 10000;
        i -= 4;
    }
    if (x < 100) {
        if (x < 10) {
            obuf[por] = '0' + x;
            ++por;
        }
        else {
            uint32_t q = (uint32_t(x) * 205) >> 11;
            uint32_t r = uint32_t(x) - q * 10;
            obuf[por] = '0' + q;
            obuf[por + 1] = '0' + r;
            por += 2;
        }
    }
    else {
        if (x < 1000) {
            memcpy(obuf + por, pre.num + (x << 2) + 1, 3);
            por += 3;
        }
        else {
            memcpy(obuf + por, pre.num + (x << 2), 4);
            por += 4;
        }
    }
    memcpy(obuf + por, buf + i + 4, 12 - i);
    por += 12 - i;
}

inline void wt() {}
template <typename Head, typename... Tail>
inline void wt(Head &&head, Tail &&...tail)
{
    wt(head);
    wt(forward<Tail>(tail)...);
}
template <typename... Args>
inline void wtn(Args &&...x)
{
    wt(forward<Args>(x)...);
    wt('\n');
}

struct Dummy {
    Dummy() { atexit(flush); }
} dummy;

} // namespace fastio
using fastio::rd;
using fastio::skip_space;
using fastio::wt;
using fastio::wtn;
ll a[nax];

int main()
{
    rd(n);
    for (int i = 1; i <= n; i++)
        rd(a[i]);
    a[0] = a[n + 1] = oo;
    for (int i = 0; i <= n + 1; i++) {
        getsum.update(i, a[i]);
        getmax.update(i, a[i]);
    }
    intervals.build();
    set<pair<int, int>> alive;
    auto good = [&](int l, int r) {
        if (r - l + 1 <= 2) return false;
        return getsum.query(l + 1, r - 1) < min(a[l], a[r]);
    };
    auto wsadz = [&](int l, int r, int x) {
        if (x == +1) {
            if (!alive.count({l, r})) {
                alive.emplace(l, r);
                intervals.add(l + 1, r - 1, +1);
            }
        }
        if (x == -1) {
            if (alive.count({l, r})) {
                alive.erase({l, r});
                intervals.add(l + 1, r - 1, -1);
            }
        }
    };
    auto wezL = [&](int l, int r) {
        return getmax.maxPrawo(l - 1, getsum.query(l, r - 1));
    };
    auto wezR = [&](int l, int r) {
        return getmax.maxLewo(r + 1, getsum.query(l + 1, r));
    };
    auto findboth = [&](int p, int x) {
        int l = p - 1, r = p + 1;
        while (1) {
            if (good(l, r)) wsadz(l, r, x);
            if (l == 0 && r == n + 1) break;
            if (a[l] < a[r])
                l = wezL(l, r);
            else
                r = wezR(l, r);
        }
    };
    auto findpresuf = [&](int p, int x) {
        int r = wezR(p, p);
        while (1) {
            if (good(p, r)) wsadz(p, r, x);
            if (r == n + 1) break;
            r = wezR(p, r);
        }
        int l = wezL(p, p);
        while (1) {
            if (good(l, p)) wsadz(l, p, x);
            if (l == 0) break;
            l = wezL(l, p);
        }
    };
    for (int i = 1; i <= n; i++) {
        findboth(i, +1);
        findpresuf(i, +1);
    }
    int q;
    cin >> q;
    while (q--) {
        int type;
        rd(type);
        if (type == 1) {
            int i, x;
            rd(i, x);
            findboth(i, -1);
            findpresuf(i, -1);
            a[i] = x;
            getsum.update(i, x);
            getmax.update(i, x);
            findboth(i, +1);
            findpresuf(i, +1);
        }
        else {
            int l, r;
            rd(l, r);
            int real_l = l, real_r = r;
            int lp = l + 1, rp = r - 1;
            while (lp <= r) {
                if (getsum.query(l, lp - 1) < a[lp]) real_l = lp;
                lp = wezR(l, lp);
            }
            while (l <= rp) {
                if (getsum.query(rp + 1, r) < a[rp]) real_r = rp;
                rp = wezL(rp, r);
            }
            wtn(intervals.query(real_l, real_r).p.second);
        }
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17