oj.uz

Submission #679535

# Submission time Handle Problem Language Result Execution time Memory
679535 2023-01-08T13:00:29 Z elkernos Fish 2 (JOI22_fish2) C++17
48 / 100
 4000 ms 17140 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define pb emplace_back
#define vt vector
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 + 213, 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 {
    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] = tree[lc] + tree[rc];
    }
    ll query(int ql, int qr, int v = 1, int l = 0, int r = n + 1)
    {
        if (r < ql || qr < l) return 0;
        if (ql <= l && r <= qr) return tree[v];
        return query(ql, qr, lc, l, m) + query(ql, qr, rc, m + 1, r);
    }
};
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);
    cin >> n;
    CMin intervals;
    Sum getsum;
    Max getmax;
    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})) {
                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;
        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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 5 ms 11272 KB Output is correct
3 Correct 5 ms 11220 KB Output is correct
4 Correct 6 ms 11348 KB Output is correct
5 Correct 25 ms 11360 KB Output is correct
6 Correct 15 ms 11368 KB Output is correct
7 Correct 18 ms 11348 KB Output is correct
8 Correct 16 ms 11368 KB Output is correct
9 Correct 14 ms 11368 KB Output is correct
10 Correct 9 ms 11348 KB Output is correct
11 Correct 7 ms 11348 KB Output is correct
12 Correct 13 ms 11372 KB Output is correct
13 Correct 12 ms 11348 KB Output is correct
14 Correct 12 ms 11364 KB Output is correct
15 Correct 15 ms 11348 KB Output is correct
16 Correct 12 ms 11360 KB Output is correct
17 Correct 14 ms 11348 KB Output is correct
18 Correct 9 ms 11348 KB Output is correct
19 Correct 11 ms 11348 KB Output is correct
20 Correct 9 ms 11372 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11348 KB Output is correct
2 Correct 1260 ms 16120 KB Output is correct
3 Correct 1729 ms 15684 KB Output is correct
4 Correct 1289 ms 16116 KB Output is correct
5 Correct 1870 ms 15676 KB Output is correct
6 Correct 398 ms 14252 KB Output is correct
7 Correct 1134 ms 13292 KB Output is correct
8 Correct 391 ms 14064 KB Output is correct
9 Correct 1282 ms 13344 KB Output is correct
10 Correct 1413 ms 13880 KB Output is correct
11 Correct 2036 ms 13752 KB Output is correct
12 Correct 588 ms 14048 KB Output is correct
13 Correct 655 ms 13876 KB Output is correct
14 Correct 520 ms 15296 KB Output is correct
15 Correct 605 ms 15128 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 5 ms 11272 KB Output is correct
3 Correct 5 ms 11220 KB Output is correct
4 Correct 6 ms 11348 KB Output is correct
5 Correct 25 ms 11360 KB Output is correct
6 Correct 15 ms 11368 KB Output is correct
7 Correct 18 ms 11348 KB Output is correct
8 Correct 16 ms 11368 KB Output is correct
9 Correct 14 ms 11368 KB Output is correct
10 Correct 9 ms 11348 KB Output is correct
11 Correct 7 ms 11348 KB Output is correct
12 Correct 13 ms 11372 KB Output is correct
13 Correct 12 ms 11348 KB Output is correct
14 Correct 12 ms 11364 KB Output is correct
15 Correct 15 ms 11348 KB Output is correct
16 Correct 12 ms 11360 KB Output is correct
17 Correct 14 ms 11348 KB Output is correct
18 Correct 9 ms 11348 KB Output is correct
19 Correct 11 ms 11348 KB Output is correct
20 Correct 9 ms 11372 KB Output is correct
21 Correct 5 ms 11348 KB Output is correct
22 Correct 1260 ms 16120 KB Output is correct
23 Correct 1729 ms 15684 KB Output is correct
24 Correct 1289 ms 16116 KB Output is correct
25 Correct 1870 ms 15676 KB Output is correct
26 Correct 398 ms 14252 KB Output is correct
27 Correct 1134 ms 13292 KB Output is correct
28 Correct 391 ms 14064 KB Output is correct
29 Correct 1282 ms 13344 KB Output is correct
30 Correct 1413 ms 13880 KB Output is correct
31 Correct 2036 ms 13752 KB Output is correct
32 Correct 588 ms 14048 KB Output is correct
33 Correct 655 ms 13876 KB Output is correct
34 Correct 520 ms 15296 KB Output is correct
35 Correct 605 ms 15128 KB Output is correct
36 Correct 1429 ms 16720 KB Output is correct
37 Correct 1818 ms 15920 KB Output is correct
38 Correct 1766 ms 15264 KB Output is correct
39 Correct 1358 ms 16552 KB Output is correct
40 Correct 1759 ms 15460 KB Output is correct
41 Correct 405 ms 14184 KB Output is correct
42 Correct 429 ms 14104 KB Output is correct
43 Correct 1094 ms 13320 KB Output is correct
44 Correct 1162 ms 13372 KB Output is correct
45 Correct 1556 ms 14304 KB Output is correct
46 Correct 1498 ms 14072 KB Output is correct
47 Correct 1847 ms 12940 KB Output is correct
48 Correct 645 ms 13892 KB Output is correct
49 Correct 603 ms 13848 KB Output is correct
50 Correct 522 ms 15288 KB Output is correct
51 Correct 544 ms 15400 KB Output is correct
52 Correct 512 ms 15264 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11348 KB Output is correct
2 Correct 1260 ms 16120 KB Output is correct
3 Correct 1729 ms 15684 KB Output is correct
4 Correct 1289 ms 16116 KB Output is correct
5 Correct 1870 ms 15676 KB Output is correct
6 Correct 398 ms 14252 KB Output is correct
7 Correct 1134 ms 13292 KB Output is correct
8 Correct 391 ms 14064 KB Output is correct
9 Correct 1282 ms 13344 KB Output is correct
10 Correct 1413 ms 13880 KB Output is correct
11 Correct 2036 ms 13752 KB Output is correct
12 Correct 588 ms 14048 KB Output is correct
13 Correct 655 ms 13876 KB Output is correct
14 Correct 520 ms 15296 KB Output is correct
15 Correct 605 ms 15128 KB Output is correct
16 Correct 10 ms 11348 KB Output is correct
17 Correct 2952 ms 16008 KB Output is correct
18 Correct 2256 ms 17076 KB Output is correct
19 Correct 2918 ms 16224 KB Output is correct
20 Correct 2846 ms 16168 KB Output is correct
21 Correct 2839 ms 16000 KB Output is correct
22 Correct 2792 ms 17140 KB Output is correct
23 Correct 2709 ms 15964 KB Output is correct
24 Correct 3124 ms 16372 KB Output is correct
25 Correct 2812 ms 16260 KB Output is correct
26 Correct 2865 ms 16464 KB Output is correct
27 Correct 697 ms 14832 KB Output is correct
28 Correct 697 ms 14704 KB Output is correct
29 Correct 682 ms 14708 KB Output is correct
30 Correct 1947 ms 13824 KB Output is correct
31 Correct 1947 ms 13664 KB Output is correct
32 Correct 2968 ms 14420 KB Output is correct
33 Correct 1914 ms 14516 KB Output is correct
34 Correct 3038 ms 14008 KB Output is correct
35 Correct 2551 ms 13492 KB Output is correct
36 Correct 2442 ms 14888 KB Output is correct
37 Correct 980 ms 14264 KB Output is correct
38 Correct 930 ms 14252 KB Output is correct
39 Correct 912 ms 15836 KB Output is correct
40 Correct 874 ms 15892 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11348 KB Output is correct
2 Correct 1260 ms 16120 KB Output is correct
3 Correct 1729 ms 15684 KB Output is correct
4 Correct 1289 ms 16116 KB Output is correct
5 Correct 1870 ms 15676 KB Output is correct
6 Correct 398 ms 14252 KB Output is correct
7 Correct 1134 ms 13292 KB Output is correct
8 Correct 391 ms 14064 KB Output is correct
9 Correct 1282 ms 13344 KB Output is correct
10 Correct 1413 ms 13880 KB Output is correct
11 Correct 2036 ms 13752 KB Output is correct
12 Correct 588 ms 14048 KB Output is correct
13 Correct 655 ms 13876 KB Output is correct
14 Correct 520 ms 15296 KB Output is correct
15 Correct 605 ms 15128 KB Output is correct
16 Correct 6 ms 11348 KB Output is correct
17 Execution timed out 4054 ms 16168 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 5 ms 11272 KB Output is correct
3 Correct 5 ms 11220 KB Output is correct
4 Correct 6 ms 11348 KB Output is correct
5 Correct 25 ms 11360 KB Output is correct
6 Correct 15 ms 11368 KB Output is correct
7 Correct 18 ms 11348 KB Output is correct
8 Correct 16 ms 11368 KB Output is correct
9 Correct 14 ms 11368 KB Output is correct
10 Correct 9 ms 11348 KB Output is correct
11 Correct 7 ms 11348 KB Output is correct
12 Correct 13 ms 11372 KB Output is correct
13 Correct 12 ms 11348 KB Output is correct
14 Correct 12 ms 11364 KB Output is correct
15 Correct 15 ms 11348 KB Output is correct
16 Correct 12 ms 11360 KB Output is correct
17 Correct 14 ms 11348 KB Output is correct
18 Correct 9 ms 11348 KB Output is correct
19 Correct 11 ms 11348 KB Output is correct
20 Correct 9 ms 11372 KB Output is correct
21 Correct 5 ms 11348 KB Output is correct
22 Correct 1260 ms 16120 KB Output is correct
23 Correct 1729 ms 15684 KB Output is correct
24 Correct 1289 ms 16116 KB Output is correct
25 Correct 1870 ms 15676 KB Output is correct
26 Correct 398 ms 14252 KB Output is correct
27 Correct 1134 ms 13292 KB Output is correct
28 Correct 391 ms 14064 KB Output is correct
29 Correct 1282 ms 13344 KB Output is correct
30 Correct 1413 ms 13880 KB Output is correct
31 Correct 2036 ms 13752 KB Output is correct
32 Correct 588 ms 14048 KB Output is correct
33 Correct 655 ms 13876 KB Output is correct
34 Correct 520 ms 15296 KB Output is correct
35 Correct 605 ms 15128 KB Output is correct
36 Correct 1429 ms 16720 KB Output is correct
37 Correct 1818 ms 15920 KB Output is correct
38 Correct 1766 ms 15264 KB Output is correct
39 Correct 1358 ms 16552 KB Output is correct
40 Correct 1759 ms 15460 KB Output is correct
41 Correct 405 ms 14184 KB Output is correct
42 Correct 429 ms 14104 KB Output is correct
43 Correct 1094 ms 13320 KB Output is correct
44 Correct 1162 ms 13372 KB Output is correct
45 Correct 1556 ms 14304 KB Output is correct
46 Correct 1498 ms 14072 KB Output is correct
47 Correct 1847 ms 12940 KB Output is correct
48 Correct 645 ms 13892 KB Output is correct
49 Correct 603 ms 13848 KB Output is correct
50 Correct 522 ms 15288 KB Output is correct
51 Correct 544 ms 15400 KB Output is correct
52 Correct 512 ms 15264 KB Output is correct
53 Correct 10 ms 11348 KB Output is correct
54 Correct 2952 ms 16008 KB Output is correct
55 Correct 2256 ms 17076 KB Output is correct
56 Correct 2918 ms 16224 KB Output is correct
57 Correct 2846 ms 16168 KB Output is correct
58 Correct 2839 ms 16000 KB Output is correct
59 Correct 2792 ms 17140 KB Output is correct
60 Correct 2709 ms 15964 KB Output is correct
61 Correct 3124 ms 16372 KB Output is correct
62 Correct 2812 ms 16260 KB Output is correct
63 Correct 2865 ms 16464 KB Output is correct
64 Correct 697 ms 14832 KB Output is correct
65 Correct 697 ms 14704 KB Output is correct
66 Correct 682 ms 14708 KB Output is correct
67 Correct 1947 ms 13824 KB Output is correct
68 Correct 1947 ms 13664 KB Output is correct
69 Correct 2968 ms 14420 KB Output is correct
70 Correct 1914 ms 14516 KB Output is correct
71 Correct 3038 ms 14008 KB Output is correct
72 Correct 2551 ms 13492 KB Output is correct
73 Correct 2442 ms 14888 KB Output is correct
74 Correct 980 ms 14264 KB Output is correct
75 Correct 930 ms 14252 KB Output is correct
76 Correct 912 ms 15836 KB Output is correct
77 Correct 874 ms 15892 KB Output is correct
78 Correct 6 ms 11348 KB Output is correct
79 Execution timed out 4054 ms 16168 KB Time limit exceeded
80 Halted 0 ms 0 KB -