Submission #679257

#	Time	Username	Problem	Language	Result	Execution time	Memory
679257		elkernos	Fish 2 (JOI22_fish2)	C++17	8 / 100	4070 ms	16272 KiB

fish2

// while (clock()<=69*CLOCKS_PER_SEC)
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("O3")
// #pragma GCC target ("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template <class c
#define ris return *this
#define dor > debug &operator<<
#define eni(x)                                                                    \
    sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \
    {
sim > struct rge {
    c b, e;
};
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c *x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef XOX
    ~debug()
    {
        cerr << endl;
    }
    eni(!=) cerr << boolalpha << i;
    ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d)
{
    ris << "" << d.first << " --> " << d.second << "";
}
sim dor(rge<c> d)
{
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
        *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
#else
    sim dor(const c &)
    {
        ris;
    }
#endif
}
;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#ifdef XOX
#warning Times may differ!!!
#endif

#define endl '\n'
#define pb emplace_back
#define vt vector
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define int long long
const int nax = 1000 * 1007, mod = 1e9 + 7;

const int tsz = 1 << 17, oo = 2e9 + 1237;
int n;

#define lc 2 * v
#define rc 2 * v + 1
#define m (l + r) / 2
struct TreeMax {
    int t[2 * tsz];
    void update(int pos, int to, int v = 1, int l = 1, int r = n)
    {
        if (l == r) {
            t[v] = to;
            return;
        }
        if (pos <= m) {
            update(pos, to, lc, l, m);
        }
        else {
            update(pos, to, rc, m + 1, r);
        }
        t[v] = max(t[lc], t[rc]);
    }
    int toRight(int ql, int qr, int big, int v = 1, int l = 1, int r = n)
    {
        if (ql > qr || t[v] < big) {
            return -oo;
        }
        if (ql == l && qr == r) {
            while (l != r) {
                if (t[rc] >= big) {
                    v = rc;
                    l = m + 1;
                }
                else {
                    v = lc;
                    r = m;
                }
            }
            return l;
        }
        return max(toRight(ql, min(qr, m), big, lc, l, m),
                   toRight(max(m + 1, ql), qr, big, rc, m + 1, r));
    }
    int toLeft(int ql, int qr, int big, int v = 1, int l = 1, int r = n)
    {
        if (ql > qr || t[v] < big) {
            return oo;
        }
        if (ql == l && qr == r) {
            while (l != r) {
                if (t[lc] >= big) {
                    v = lc;
                    r = m;
                }
                else {
                    v = rc;
                    l = m + 1;
                }
            }
            return l;
        }
        return min(toLeft(ql, min(qr, m), big, lc, l, m),
                   toLeft(max(m + 1, ql), qr, big, rc, m + 1, r));
    }
};
struct TreeSum {
    int t[2 * tsz];
    void update(int pos, int to, int v = 1, int l = 1, int r = n)
    {
        if (l == r) {
            t[v] = to;
            return;
        }
        if (pos <= m) {
            update(pos, to, lc, l, m);
        }
        else {
            update(pos, to, rc, m + 1, r);
        }
        t[v] = t[lc] + t[rc];
    }
    int query(int ql, int qr, int v = 1, int l = 1, int r = n)
    {
        if (ql > qr) {
            return 0;
        }
        if (ql == l && qr == r) {
            return t[v];
        }
        return query(ql, min(qr, m), lc, l, m) +
               query(max(m + 1, ql), qr, rc, m + 1, r);
    }
};
struct TreeCMin {
    pii lacz(const pii &a, const pii &b)
    {
        if (a.first == b.first) return pii{a.first, a.second + b.second};
        return min(a, b);
    }
    pii t[2 * tsz];
    int offset[2 * tsz];
    void push(int v)
    {
        for (auto to : {lc, rc}) {
            offset[to] += offset[v];
            t[to].first += offset[v];
        }
        offset[v] = 0;
    }
    void build(int v = 1, int l = 1, int r = n)
    {
        if (l == r) {
            t[v] = pii{0, 1};
            return;
        }
        build(lc, l, m);
        build(rc, m + 1, r);
        t[v] = lacz(t[lc], t[rc]);
    }
    void update(int ql, int qr, int ile, int v = 1, int l = 1, int r = n)
    {
        if (l != r) {
            push(v);
        }
        if (ql > qr) {
            return;
        }
        if (ql == l && r == qr) {
            t[v].first += ile;
            offset[v] += ile;
            return;
        }
        update(ql, min(m, qr), ile, lc, l, m);
        update(max(m + 1, ql), qr, ile, rc, m + 1, r);
        t[v] = lacz(t[lc], t[rc]);
    }
    pii query(int ql, int qr, int v = 1, int l = 1, int r = n)
    {
        if (l != r) {
            push(v);
        }
        if (ql > qr) {
            return pii{oo, oo};
        }
        if (ql == l && qr == r) {
            return t[v];
        }
        return lacz(query(ql, min(qr, m), lc, l, m),
                    query(max(m + 1, ql), qr, rc, m + 1, r));
    }
};

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    vt<int> a(n + 2);
    set<pii> active;
    TreeMax one;
    TreeSum two;
    TreeCMin three;
    auto gitcheck = [&](int l, int r) {
        if (!(1 <= l && l <= r && r <= n)) {
            return false;
        }
        return two.query(l, r) < min(a[l - 1], a[r + 1]);
    };
    auto nextRight = [&](int l, int r) {
        int sum = two.query(l, r);
        return one.toLeft(r + 1, n, sum);
    };
    auto nextLeft = [&](int l, int r) {
        int sum = two.query(l, r);
        return one.toRight(1, l - 1, sum);
    };
    auto maybe = [&](int l, int r, int x) {
        if (x == +1) {
            if (!active.count({l, r})) {
                active.emplace(l, r);
                debug() << imie(l) imie(r) imie(x);
                three.update(l, r, x);
            }
        }
        else {
            if (active.count({l, r})) {
                active.erase({l, r});
                debug() << imie(l) imie(r) imie(x);
                three.update(l, r, x);
            }
        }
    };
    auto both = [&](int pos, int x) {
        int l = pos, r = pos;
        while (1 <= l && r <= n) {
            if (gitcheck(l, r)) {
                maybe(l, r, x);
            }
            if (a[l - 1] < a[r + 1]) {
                l = nextLeft(l, r);
                if (gitcheck(l + 1, r)) {
                    maybe(l + 1, r, x);
                    if (nextLeft(l + 1, r) != l) {
                        l++;
                    }
                }
            }
            else {
                r = nextRight(l, r);
                if (gitcheck(l, r - 1)) {
                    maybe(l, r - 1, x);
                    if (nextRight(l, r - 1) != r) {
                        r--;
                    }
                }
            }
        }
    };
    auto liczpre = [&](int pos, int x) {
        {
            int l = pos, r = pos;
            while (1 <= l && r <= n) {
                if (gitcheck(l, r)) {
                    maybe(l, r, x);
                }
                r = nextRight(l, r);
                if (gitcheck(l, r - 1)) {
                    maybe(l, r - 1, x);
                }
            }
        }
        {
            int l = pos, r = pos;
            while (1 <= l && r <= n) {
                if (gitcheck(l, r)) {
                    maybe(l, r, x);
                }
                l = nextLeft(l, r);
                if (gitcheck(l + 1, r)) {
                    maybe(l + 1, r, x);
                }
            }
        }
        if (gitcheck(pos + 1, n)) {
            maybe(pos + 1, n, x);
        }
        if (gitcheck(1, pos - 1)) {
            maybe(1, pos - 1, x);
        }
        if (gitcheck(pos, n)) {
            maybe(pos, n, x);
        }
        if (gitcheck(1, pos)) {
            maybe(1, pos, x);
        }
    };
    a[0] = a[n + 1] = oo * oo;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        one.update(i, a[i]);
        two.update(i, a[i]);
    }
    three.build();
    for (int i = 1; i <= n; i++) {
        both(i, +1);
        liczpre(i, +1);
    }
    int q;
    cin >> q;
    while (q--) {
        debug() << imie(a) imie(active);
        int type, pos, to;
        cin >> type >> pos >> to;
        if (type == 1) {
            both(pos, -1);
            liczpre(pos, -1);
            liczpre(pos + 1, -1);
            liczpre(pos + 1, -1);
            liczpre(pos - 1, -1);
            a[pos] = to;
            one.update(pos, a[pos]);
            two.update(pos, a[pos]);
            both(pos, +1);
            liczpre(pos, +1);
            liczpre(pos + 1, +1);
            liczpre(pos - 1, +1);
        }
        else {
            int l = pos, r = to;
            int pre = pos;
            int rpre = l, rsuf = r;
            {
                while (pre <= r) {
                    if (two.query(l, pre - 1) < a[pre]) {
                        rpre = pre;
                    }
                    pre = nextRight(l, pre);
                }
            }
            int suf = to;
            {
                while (suf >= l) {
                    if (two.query(suf + 1, r) < a[suf]) {
                        rsuf = suf;
                    }
                    suf = nextLeft(suf, r);
                }
            }
            debug() << imie(rpre) imie(rsuf);
            cout << three.query(rpre, rsuf).second << endl;
        }
    }
}

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