oj.uz

Submission #679526

# Submission time Handle Problem Language Result Execution time Memory
679526 2023-01-08T12:50:10 Z elkernos Fish 2 (JOI22_fish2) C++17
43 / 100
 3131 ms 16676 KB 
// 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>

using namespace std;

#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;

const int nax = 100 * 1007;
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 = {{n + 5, 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[4 * 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);
    }
};
struct Sum {
    typedef ll T;
    static constexpr T unit = 0;
    T f(T a, T b) { return a + b; } // (any associative fn)
    vector<T> s;
    int n;
    Sum(int nd = nax, T def = unit) : s(2 * nd, def), n(nd) {}
    void update(int pos, T val)
    {
        for (s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e)
    {
        T ra = unit, rb = unit;
        for (b += n, e += n + 1; b < e; b /= 2, e /= 2) {
            if (b % 2) ra = f(ra, s[b++]);
            if (e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};
struct Max {
    ll tree[4 * 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);
    }
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    CMin intervals;
    Sum getsum;
    Max getmax;
    cin >> n;
    vt<ll> a(n + 2);
    for (int i = 1; i <= n; i++)
        cin >> 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})) {
                debug() << imie(l) imie(r) imie(x);
                alive.emplace(l, r);
                intervals.add(l + 1, r - 1, +1);
            }
        }
        if (x == -1) {
            if (alive.count({l, r})) {
                debug() << imie(l) imie(r) imie(x);
                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;
        cin >> type;
        if (type == 1) {
            int i, x;
            cin >> 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;
            cin >> 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);
            }
            cout << intervals.query(real_l, real_r).p.second << endl;
        }
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Incorrect 15 ms 9752 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9744 KB Output is correct
2 Correct 686 ms 14756 KB Output is correct
3 Correct 948 ms 13980 KB Output is correct
4 Correct 705 ms 14540 KB Output is correct
5 Correct 924 ms 14112 KB Output is correct
6 Correct 228 ms 12616 KB Output is correct
7 Correct 603 ms 11748 KB Output is correct
8 Correct 221 ms 12520 KB Output is correct
9 Correct 578 ms 11972 KB Output is correct
10 Correct 696 ms 12492 KB Output is correct
11 Correct 944 ms 12232 KB Output is correct
12 Correct 335 ms 12308 KB Output is correct
13 Correct 339 ms 12368 KB Output is correct
14 Correct 284 ms 13644 KB Output is correct
15 Correct 273 ms 13532 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Incorrect 15 ms 9752 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9744 KB Output is correct
2 Correct 686 ms 14756 KB Output is correct
3 Correct 948 ms 13980 KB Output is correct
4 Correct 705 ms 14540 KB Output is correct
5 Correct 924 ms 14112 KB Output is correct
6 Correct 228 ms 12616 KB Output is correct
7 Correct 603 ms 11748 KB Output is correct
8 Correct 221 ms 12520 KB Output is correct
9 Correct 578 ms 11972 KB Output is correct
10 Correct 696 ms 12492 KB Output is correct
11 Correct 944 ms 12232 KB Output is correct
12 Correct 335 ms 12308 KB Output is correct
13 Correct 339 ms 12368 KB Output is correct
14 Correct 284 ms 13644 KB Output is correct
15 Correct 273 ms 13532 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Incorrect 1573 ms 15616 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9744 KB Output is correct
2 Correct 686 ms 14756 KB Output is correct
3 Correct 948 ms 13980 KB Output is correct
4 Correct 705 ms 14540 KB Output is correct
5 Correct 924 ms 14112 KB Output is correct
6 Correct 228 ms 12616 KB Output is correct
7 Correct 603 ms 11748 KB Output is correct
8 Correct 221 ms 12520 KB Output is correct
9 Correct 578 ms 11972 KB Output is correct
10 Correct 696 ms 12492 KB Output is correct
11 Correct 944 ms 12232 KB Output is correct
12 Correct 335 ms 12308 KB Output is correct
13 Correct 339 ms 12368 KB Output is correct
14 Correct 284 ms 13644 KB Output is correct
15 Correct 273 ms 13532 KB Output is correct
16 Correct 4 ms 9684 KB Output is correct
17 Correct 3068 ms 15424 KB Output is correct
18 Correct 2423 ms 16620 KB Output is correct
19 Correct 2740 ms 15708 KB Output is correct
20 Correct 2048 ms 16676 KB Output is correct
21 Correct 2825 ms 16280 KB Output is correct
22 Correct 2353 ms 16528 KB Output is correct
23 Correct 3131 ms 15708 KB Output is correct
24 Correct 2293 ms 16648 KB Output is correct
25 Correct 2863 ms 15660 KB Output is correct
26 Correct 766 ms 15436 KB Output is correct
27 Correct 995 ms 15288 KB Output is correct
28 Correct 1527 ms 15488 KB Output is correct
29 Correct 864 ms 15296 KB Output is correct
30 Correct 980 ms 15324 KB Output is correct
31 Correct 1688 ms 15296 KB Output is correct
32 Correct 2254 ms 15868 KB Output is correct
33 Correct 1608 ms 13816 KB Output is correct
34 Correct 1946 ms 16572 KB Output is correct
35 Correct 1350 ms 14432 KB Output is correct
36 Correct 2047 ms 15540 KB Output is correct
37 Correct 1441 ms 15276 KB Output is correct
38 Correct 1046 ms 14980 KB Output is correct
39 Correct 958 ms 15948 KB Output is correct
40 Correct 600 ms 15960 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Incorrect 15 ms 9752 KB Output isn't correct
6 Halted 0 ms 0 KB -