oj.uz

Submission #679589

# Submission time Handle Problem Language Result Execution time Memory
679589 2023-01-08T15:40:36 Z elkernos Fish 2 (JOI22_fish2) C++17
31 / 100
 1407 ms 11908 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);
        if (type == 1) {
            int i, x;
            scanf("%d%d", &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;
            scanf("%d%d", &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);
            }
            printf("%d\n", intervals.query(real_l, real_r).p.second);
        }
    }
}

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:187:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
fish2.cpp:190:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |         scanf("%d", &type);
      |         ~~~~~^~~~~~~~~~~~~
fish2.cpp:193:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |             scanf("%d%d", &i, &x);
      |             ~~~~~^~~~~~~~~~~~~~~~
fish2.cpp:204:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |             scanf("%d%d", &l, &r);
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 597 ms 11016 KB Output is correct
3 Correct 723 ms 10496 KB Output is correct
4 Correct 588 ms 10952 KB Output is correct
5 Correct 729 ms 10584 KB Output is correct
6 Correct 179 ms 9036 KB Output is correct
7 Correct 396 ms 8188 KB Output is correct
8 Correct 180 ms 8948 KB Output is correct
9 Correct 392 ms 8172 KB Output is correct
10 Correct 551 ms 8780 KB Output is correct
11 Correct 673 ms 8712 KB Output is correct
12 Correct 235 ms 8816 KB Output is correct
13 Correct 242 ms 8844 KB Output is correct
14 Correct 231 ms 10180 KB Output is correct
15 Correct 238 ms 10092 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 597 ms 11016 KB Output is correct
3 Correct 723 ms 10496 KB Output is correct
4 Correct 588 ms 10952 KB Output is correct
5 Correct 729 ms 10584 KB Output is correct
6 Correct 179 ms 9036 KB Output is correct
7 Correct 396 ms 8188 KB Output is correct
8 Correct 180 ms 8948 KB Output is correct
9 Correct 392 ms 8172 KB Output is correct
10 Correct 551 ms 8780 KB Output is correct
11 Correct 673 ms 8712 KB Output is correct
12 Correct 235 ms 8816 KB Output is correct
13 Correct 242 ms 8844 KB Output is correct
14 Correct 231 ms 10180 KB Output is correct
15 Correct 238 ms 10092 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1212 ms 11052 KB Output is correct
18 Correct 1037 ms 11884 KB Output is correct
19 Correct 1193 ms 11084 KB Output is correct
20 Correct 1178 ms 11004 KB Output is correct
21 Correct 1133 ms 11044 KB Output is correct
22 Correct 1027 ms 11908 KB Output is correct
23 Correct 1115 ms 10864 KB Output is correct
24 Correct 1230 ms 11296 KB Output is correct
25 Correct 1191 ms 11164 KB Output is correct
26 Correct 1233 ms 11276 KB Output is correct
27 Correct 370 ms 9544 KB Output is correct
28 Correct 367 ms 9768 KB Output is correct
29 Correct 364 ms 9536 KB Output is correct
30 Correct 730 ms 8392 KB Output is correct
31 Correct 712 ms 8496 KB Output is correct
32 Correct 1144 ms 9112 KB Output is correct
33 Correct 834 ms 9324 KB Output is correct
34 Correct 1154 ms 8728 KB Output is correct
35 Correct 968 ms 8600 KB Output is correct
36 Correct 1026 ms 9500 KB Output is correct
37 Correct 404 ms 9036 KB Output is correct
38 Correct 400 ms 9196 KB Output is correct
39 Correct 435 ms 10704 KB Output is correct
40 Correct 424 ms 10656 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 597 ms 11016 KB Output is correct
3 Correct 723 ms 10496 KB Output is correct
4 Correct 588 ms 10952 KB Output is correct
5 Correct 729 ms 10584 KB Output is correct
6 Correct 179 ms 9036 KB Output is correct
7 Correct 396 ms 8188 KB Output is correct
8 Correct 180 ms 8948 KB Output is correct
9 Correct 392 ms 8172 KB Output is correct
10 Correct 551 ms 8780 KB Output is correct
11 Correct 673 ms 8712 KB Output is correct
12 Correct 235 ms 8816 KB Output is correct
13 Correct 242 ms 8844 KB Output is correct
14 Correct 231 ms 10180 KB Output is correct
15 Correct 238 ms 10092 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Incorrect 1407 ms 11040 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -