oj.uz

Submission #685428

# Submission time Handle Problem Language Result Execution time Memory
685428 2023-01-24T10:44:46 Z elkernos Fish 2 (JOI22_fish2) C++17
60 / 100
 4000 ms 13292 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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;

ll a[nax];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &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;
    scanf("%d", &q);
    while (q--) {
        int type;
        scanf("%d", &type);
        auto pisz = [&](int i, ll x) {
            findboth(i, -1);
            findpresuf(i, -1);
            getsum.update(i, x - a[i]);
            a[i] = x;
            getmax.update(i, x);
            findboth(i, +1);
            findpresuf(i, +1);
        };
        if (type == 1) {
            int i, x;
            scanf("%d%d", &i, &x);
            pisz(i, x);
        }
        else {
            int l, r;
            scanf("%d%d", &l, &r);
            int bylo_lewo = a[l - 1], bylo_prawo = a[r + 1];
            ll pisz_sum = getsum.query(l, r) + 1;
            if (l != 1) pisz(l - 1, pisz_sum);
            if (r != n) pisz(r + 1, pisz_sum);
            printf("%d\n", intervals.query(l, r).p.second);
            if (l != 1) pisz(l - 1, bylo_lewo);
            if (r != n) pisz(r + 1, bylo_prawo);
        }
    }
}

Compilation message

fish2.cpp: In function 'int main()':
fish2.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
fish2.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         scanf("%lld", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
fish2.cpp:185:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
fish2.cpp:188:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         scanf("%d", &type);
      |         ~~~~~^~~~~~~~~~~~~
fish2.cpp:200:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |             scanf("%d%d", &i, &x);
      |             ~~~~~^~~~~~~~~~~~~~~~
fish2.cpp:205:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  205 |             scanf("%d%d", &l, &r);
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 13 ms 324 KB Output is correct
6 Correct 21 ms 340 KB Output is correct
7 Correct 11 ms 316 KB Output is correct
8 Correct 28 ms 324 KB Output is correct
9 Correct 22 ms 340 KB Output is correct
10 Correct 6 ms 324 KB Output is correct
11 Correct 10 ms 340 KB Output is correct
12 Correct 8 ms 340 KB Output is correct
13 Correct 17 ms 404 KB Output is correct
14 Correct 7 ms 340 KB Output is correct
15 Correct 12 ms 412 KB Output is correct
16 Correct 14 ms 340 KB Output is correct
17 Correct 8 ms 316 KB Output is correct
18 Correct 16 ms 340 KB Output is correct
19 Correct 7 ms 340 KB Output is correct
20 Correct 11 ms 408 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 619 ms 11672 KB Output is correct
3 Correct 750 ms 10764 KB Output is correct
4 Correct 614 ms 11596 KB Output is correct
5 Correct 734 ms 11032 KB Output is correct
6 Correct 187 ms 9944 KB Output is correct
7 Correct 412 ms 8328 KB Output is correct
8 Correct 185 ms 9928 KB Output is correct
9 Correct 419 ms 8416 KB Output is correct
10 Correct 570 ms 9524 KB Output is correct
11 Correct 699 ms 8972 KB Output is correct
12 Correct 237 ms 9004 KB Output is correct
13 Correct 241 ms 9068 KB Output is correct
14 Correct 241 ms 10808 KB Output is correct
15 Correct 246 ms 10676 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 13 ms 324 KB Output is correct
6 Correct 21 ms 340 KB Output is correct
7 Correct 11 ms 316 KB Output is correct
8 Correct 28 ms 324 KB Output is correct
9 Correct 22 ms 340 KB Output is correct
10 Correct 6 ms 324 KB Output is correct
11 Correct 10 ms 340 KB Output is correct
12 Correct 8 ms 340 KB Output is correct
13 Correct 17 ms 404 KB Output is correct
14 Correct 7 ms 340 KB Output is correct
15 Correct 12 ms 412 KB Output is correct
16 Correct 14 ms 340 KB Output is correct
17 Correct 8 ms 316 KB Output is correct
18 Correct 16 ms 340 KB Output is correct
19 Correct 7 ms 340 KB Output is correct
20 Correct 11 ms 408 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 619 ms 11672 KB Output is correct
23 Correct 750 ms 10764 KB Output is correct
24 Correct 614 ms 11596 KB Output is correct
25 Correct 734 ms 11032 KB Output is correct
26 Correct 187 ms 9944 KB Output is correct
27 Correct 412 ms 8328 KB Output is correct
28 Correct 185 ms 9928 KB Output is correct
29 Correct 419 ms 8416 KB Output is correct
30 Correct 570 ms 9524 KB Output is correct
31 Correct 699 ms 8972 KB Output is correct
32 Correct 237 ms 9004 KB Output is correct
33 Correct 241 ms 9068 KB Output is correct
34 Correct 241 ms 10808 KB Output is correct
35 Correct 246 ms 10676 KB Output is correct
36 Correct 707 ms 12128 KB Output is correct
37 Correct 854 ms 11040 KB Output is correct
38 Correct 782 ms 10632 KB Output is correct
39 Correct 686 ms 12224 KB Output is correct
40 Correct 806 ms 10548 KB Output is correct
41 Correct 238 ms 9920 KB Output is correct
42 Correct 207 ms 10032 KB Output is correct
43 Correct 450 ms 8524 KB Output is correct
44 Correct 474 ms 8412 KB Output is correct
45 Correct 740 ms 9796 KB Output is correct
46 Correct 671 ms 9460 KB Output is correct
47 Correct 678 ms 8200 KB Output is correct
48 Correct 272 ms 9088 KB Output is correct
49 Correct 301 ms 9124 KB Output is correct
50 Correct 260 ms 10700 KB Output is correct
51 Correct 297 ms 10796 KB Output is correct
52 Correct 288 ms 10788 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 619 ms 11672 KB Output is correct
3 Correct 750 ms 10764 KB Output is correct
4 Correct 614 ms 11596 KB Output is correct
5 Correct 734 ms 11032 KB Output is correct
6 Correct 187 ms 9944 KB Output is correct
7 Correct 412 ms 8328 KB Output is correct
8 Correct 185 ms 9928 KB Output is correct
9 Correct 419 ms 8416 KB Output is correct
10 Correct 570 ms 9524 KB Output is correct
11 Correct 699 ms 8972 KB Output is correct
12 Correct 237 ms 9004 KB Output is correct
13 Correct 241 ms 9068 KB Output is correct
14 Correct 241 ms 10808 KB Output is correct
15 Correct 246 ms 10676 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Execution timed out 4046 ms 11724 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 619 ms 11672 KB Output is correct
3 Correct 750 ms 10764 KB Output is correct
4 Correct 614 ms 11596 KB Output is correct
5 Correct 734 ms 11032 KB Output is correct
6 Correct 187 ms 9944 KB Output is correct
7 Correct 412 ms 8328 KB Output is correct
8 Correct 185 ms 9928 KB Output is correct
9 Correct 419 ms 8416 KB Output is correct
10 Correct 570 ms 9524 KB Output is correct
11 Correct 699 ms 8972 KB Output is correct
12 Correct 237 ms 9004 KB Output is correct
13 Correct 241 ms 9068 KB Output is correct
14 Correct 241 ms 10808 KB Output is correct
15 Correct 246 ms 10676 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 2588 ms 12668 KB Output is correct
18 Correct 2003 ms 13164 KB Output is correct
19 Correct 2128 ms 12136 KB Output is correct
20 Correct 1738 ms 13012 KB Output is correct
21 Correct 2403 ms 12700 KB Output is correct
22 Correct 1995 ms 13112 KB Output is correct
23 Correct 2437 ms 12176 KB Output is correct
24 Correct 1936 ms 13292 KB Output is correct
25 Correct 2215 ms 12164 KB Output is correct
26 Correct 661 ms 11784 KB Output is correct
27 Correct 839 ms 11796 KB Output is correct
28 Correct 1140 ms 11784 KB Output is correct
29 Correct 749 ms 11784 KB Output is correct
30 Correct 830 ms 11760 KB Output is correct
31 Correct 1375 ms 11836 KB Output is correct
32 Correct 1844 ms 12548 KB Output is correct
33 Correct 1156 ms 10488 KB Output is correct
34 Correct 1672 ms 13272 KB Output is correct
35 Correct 994 ms 11064 KB Output is correct
36 Correct 1660 ms 12040 KB Output is correct
37 Correct 1190 ms 11588 KB Output is correct
38 Correct 795 ms 11476 KB Output is correct
39 Correct 844 ms 12476 KB Output is correct
40 Correct 515 ms 12364 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 13 ms 324 KB Output is correct
6 Correct 21 ms 340 KB Output is correct
7 Correct 11 ms 316 KB Output is correct
8 Correct 28 ms 324 KB Output is correct
9 Correct 22 ms 340 KB Output is correct
10 Correct 6 ms 324 KB Output is correct
11 Correct 10 ms 340 KB Output is correct
12 Correct 8 ms 340 KB Output is correct
13 Correct 17 ms 404 KB Output is correct
14 Correct 7 ms 340 KB Output is correct
15 Correct 12 ms 412 KB Output is correct
16 Correct 14 ms 340 KB Output is correct
17 Correct 8 ms 316 KB Output is correct
18 Correct 16 ms 340 KB Output is correct
19 Correct 7 ms 340 KB Output is correct
20 Correct 11 ms 408 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 619 ms 11672 KB Output is correct
23 Correct 750 ms 10764 KB Output is correct
24 Correct 614 ms 11596 KB Output is correct
25 Correct 734 ms 11032 KB Output is correct
26 Correct 187 ms 9944 KB Output is correct
27 Correct 412 ms 8328 KB Output is correct
28 Correct 185 ms 9928 KB Output is correct
29 Correct 419 ms 8416 KB Output is correct
30 Correct 570 ms 9524 KB Output is correct
31 Correct 699 ms 8972 KB Output is correct
32 Correct 237 ms 9004 KB Output is correct
33 Correct 241 ms 9068 KB Output is correct
34 Correct 241 ms 10808 KB Output is correct
35 Correct 246 ms 10676 KB Output is correct
36 Correct 707 ms 12128 KB Output is correct
37 Correct 854 ms 11040 KB Output is correct
38 Correct 782 ms 10632 KB Output is correct
39 Correct 686 ms 12224 KB Output is correct
40 Correct 806 ms 10548 KB Output is correct
41 Correct 238 ms 9920 KB Output is correct
42 Correct 207 ms 10032 KB Output is correct
43 Correct 450 ms 8524 KB Output is correct
44 Correct 474 ms 8412 KB Output is correct
45 Correct 740 ms 9796 KB Output is correct
46 Correct 671 ms 9460 KB Output is correct
47 Correct 678 ms 8200 KB Output is correct
48 Correct 272 ms 9088 KB Output is correct
49 Correct 301 ms 9124 KB Output is correct
50 Correct 260 ms 10700 KB Output is correct
51 Correct 297 ms 10796 KB Output is correct
52 Correct 288 ms 10788 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Execution timed out 4046 ms 11724 KB Time limit exceeded
55 Halted 0 ms 0 KB -