oj.uz

Submission #872275

# Submission time Handle Problem Language Result Execution time Memory
872275 2023-11-12T16:54:42 Z green_gold_dog Sequence (APIO23_sequence) C++17
50 / 100
 2000 ms 68616 KB 
#pragma GCC optimize("Ofast")

#include "sequence.h"

#include <bits/stdc++.h>

using namespace std;

typedef int ll;

const ll INF = 1'000'000'000;

struct segment_tree_min {
        vector<ll> tree, m;
        ll size;
        segment_tree_min(ll n) {
                size = 1;
                while (size < n) {
                        size *= 2;
                }
                tree.resize(size * 2, 0);
                m.resize(size * 2, 0);
        }
        void add(ll v, ll x) {
                tree[v] += x;
                m[v] += x;
        }
        void push(ll v) {
                add(v * 2, m[v]);
                add(v * 2 + 1, m[v]);
                m[v] = 0;
        }
        ll get(ll l, ll r) {
                return get(1, 0, size, l, r);
        }
        ll get(ll v, ll l, ll r, ll ql, ll qr) {
                if (ql <= l && r <= qr) {
                        return tree[v];
                }
                if (qr <= l || r <= ql) {
                        return INF;
                }
                push(v);
                ll mid = (l + r) / 2;
                return min(get(v * 2, l, mid, ql, qr), get(v * 2 + 1, mid, r, ql, qr));
        }
        void add(ll l, ll r, ll x) {
                add(1, 0, size, l, r, x);
        }
        void add(ll v, ll l, ll r, ll ql, ll qr, ll x) {
                if (ql <= l && r <= qr) {
                        add(v, x);
                        return;
                }
                if (qr <= l || r <= ql) {
                        return;
                }
                push(v);
                ll mid = (l + r) / 2;
                add(v * 2, l, mid, ql, qr, x);
                add(v * 2 + 1, mid, r, ql, qr, x);
                tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
        }
};

struct segment_tree_max {
        vector<ll> tree, m;
        ll size;
        segment_tree_max(ll n) {
                size = 1;
                while (size < n) {
                        size *= 2;
                }
                tree.resize(size * 2, 0);
                m.resize(size * 2, 0);
        }
        void add(ll v, ll x) {
                tree[v] += x;
                m[v] += x;
        }
        void push(ll v) {
                add(v * 2, m[v]);
                add(v * 2 + 1, m[v]);
                m[v] = 0;
        }
        ll get(ll l, ll r) {
                return get(1, 0, size, l, r);
        }
        ll get(ll v, ll l, ll r, ll ql, ll qr) {
                if (ql <= l && r <= qr) {
                        return tree[v];
                }
                if (qr <= l || r <= ql) {
                        return -INF;
                }
                push(v);
                ll mid = (l + r) / 2;
                return max(get(v * 2, l, mid, ql, qr), get(v * 2 + 1, mid, r, ql, qr));
        }
        void add(ll l, ll r, ll x) {
                add(1, 0, size, l, r, x);
        }
        void add(ll v, ll l, ll r, ll ql, ll qr, ll x) {
                if (ql <= l && r <= qr) {
                        add(v, x);
                        return;
                }
                if (qr <= l || r <= ql) {
                        return;
                }
                push(v);
                ll mid = (l + r) / 2;
                add(v * 2, l, mid, ql, qr, x);
                add(v * 2 + 1, mid, r, ql, qr, x);
                tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
        }
};

struct segment_tree_sum {
        vector<ll> tree;
        ll size;
        segment_tree_sum(ll n) {
                size = 1;
                while (size < n) {
                        size *= 2;
                }
                tree.resize(size * 2, 0);
        }
        ll get(ll l, ll r) {
                return get(1, 0, size, l, r);
        }
        ll get(ll v, ll l, ll r, ll ql, ll qr) {
                if (ql <= l && r <= qr) {
                        return tree[v];
                }
                if (qr <= l || r <= ql) {
                        return 0;
                }
                ll mid = (l + r) / 2;
                return get(v * 2, l, mid, ql, qr) + get(v * 2 + 1, mid, r, ql, qr);
        }
        void add(ll x, ll y) {
                add(1, 0, size, x, y);
        }
        void add(ll v, ll l, ll r, ll x, ll y) {
                if (x < l || r <= x) {
                        return;
                }
                if (r - l == 1) {
                        tree[v] += y;
                        return;
                }
                ll mid = (l + r) / 2;
                add(v * 2, l, mid, x, y);
                add(v * 2 + 1, mid, r, x, y);
                tree[v] = tree[v * 2] + tree[v * 2 + 1];
        }
};

ll sequence(ll n, vector<ll> a) {
        segment_tree_min sti(n), stir(n);
        segment_tree_max sta(n), star(n);
        segment_tree_sum st(n);
        vector<vector<ll>> all(n);
        for (ll i = 0; i < n; i++) {
                sti.add(i, n, 1);
                sta.add(i, n, 1);
                stir.add(0, i + 1, 1);
                star.add(0, i + 1, 1);
                st.add(i, 1);
                all[a[i] - 1].push_back(i);
        }
        ll ans = 0;
        for (ll i = 0; i < n; i++) {
                for (auto j : all[i]) {
                        sti.add(j, n, -1);
                        sti.add(j, n, -1);
                        stir.add(0, j + 1, -1);
                        star.add(0, j + 1, -1);
                        st.add(j, -1);
                }
                ll lst = 0;
                for (ll j = 0; j < all[i].size(); j++) {
                        ll x = all[i][j];
                        sti.add(x, n, 1);
                        sta.add(x, n, -1);
                        ll m = st.get(0, all[i][j]), m2 = st.get(all[i][j], n);
                        ll mmi = stir.get(lst, all[i][j] + 1) - m2 - m, mma = star.get(lst, all[i][j] + 1) - m2 - m;
                        ll ql = all[i][j], qr = n;
                        ll v = 1, l = 0, r = sti.size;
                        while (r - l > 1) {
                                ll mid = (l + r) / 2;
                                if (mid < ql) {
                                        l = mid;
                                        v = v * 2 + 1;
                                        continue;
                                }
                                ll mi = sti.get(max(mid, ql), min(r, qr)) + mmi, ma = sta.get(max(mid, ql), min(r, qr)) + mma;
                                if ((mi <= -1 && ma >= -1) || (mi <= 0 && ma >= 0) || (mi <= 1 && ma >= 1)) {
                                        v = v * 2 + 1;
                                        l = mid;
                                } else {
                                        v = v * 2;
                                        r = mid;
                                }
                        }
                        ans = max(ans, (ll)((lower_bound(all[i].begin(), all[i].end(), r) - all[i].begin()) - j));
                }
                for (auto j : all[i]) {
                        sti.add(j, n, -1);
                        sta.add(j, n, -1);
                        stir.add(0, j + 1, -1);
                        star.add(0, j + 1, -1);
                        st.add(j, -1);
                }
        }
        return ans;
}

Compilation message

sequence.cpp: In function 'll sequence(ll, std::vector<int>)':
sequence.cpp:183:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |                 for (ll j = 0; j < all[i].size(); j++) {
      |                                ~~^~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 8 ms 604 KB Output is correct
14 Correct 7 ms 680 KB Output is correct
15 Correct 7 ms 604 KB Output is correct
16 Correct 8 ms 604 KB Output is correct
17 Correct 7 ms 600 KB Output is correct
18 Correct 6 ms 604 KB Output is correct
19 Correct 7 ms 604 KB Output is correct
20 Correct 7 ms 672 KB Output is correct
21 Correct 7 ms 604 KB Output is correct
22 Correct 7 ms 672 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Execution timed out 2062 ms 63060 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 2029 ms 56164 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2015 ms 68616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 8 ms 604 KB Output is correct
14 Correct 7 ms 680 KB Output is correct
15 Correct 7 ms 604 KB Output is correct
16 Correct 8 ms 604 KB Output is correct
17 Correct 7 ms 600 KB Output is correct
18 Correct 6 ms 604 KB Output is correct
19 Correct 7 ms 604 KB Output is correct
20 Correct 7 ms 672 KB Output is correct
21 Correct 7 ms 604 KB Output is correct
22 Correct 7 ms 672 KB Output is correct
23 Correct 533 ms 13788 KB Output is correct
24 Correct 535 ms 13908 KB Output is correct
25 Correct 532 ms 13792 KB Output is correct
26 Correct 507 ms 12624 KB Output is correct
27 Correct 493 ms 12980 KB Output is correct
28 Correct 469 ms 12860 KB Output is correct
29 Correct 437 ms 12584 KB Output is correct
30 Correct 452 ms 12764 KB Output is correct
31 Correct 468 ms 12752 KB Output is correct
32 Correct 477 ms 14712 KB Output is correct
33 Correct 514 ms 13392 KB Output is correct
34 Correct 525 ms 13392 KB Output is correct
35 Correct 520 ms 13548 KB Output is correct
36 Correct 522 ms 13652 KB Output is correct
37 Correct 533 ms 13576 KB Output is correct
38 Correct 530 ms 13608 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 8 ms 604 KB Output is correct
14 Correct 7 ms 680 KB Output is correct
15 Correct 7 ms 604 KB Output is correct
16 Correct 8 ms 604 KB Output is correct
17 Correct 7 ms 600 KB Output is correct
18 Correct 6 ms 604 KB Output is correct
19 Correct 7 ms 604 KB Output is correct
20 Correct 7 ms 672 KB Output is correct
21 Correct 7 ms 604 KB Output is correct
22 Correct 7 ms 672 KB Output is correct
23 Execution timed out 2062 ms 63060 KB Time limit exceeded
24 Halted 0 ms 0 KB -