oj.uz

Submission #760270

# Submission time Handle Problem Language Result Execution time Memory
760270 2023-06-17T11:27:56 Z danikoynov Sequence (APIO23_sequence) C++17
100 / 100
 1144 ms 55512 KB 
#include "sequence.h"

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 10;

struct node
{
    int lb, rb;

    node(int _lb = 1e9, int _rb = -1e9)
    {
        lb = _lb;
        rb = _rb;
    }
};

node merge_node(node lf, node rf)
{
    node nd;
    nd.lb = min(lf.lb, rf.lb);
    nd.rb = max(lf.rb, rf.rb);
    return nd;
}

node tree[4 * maxn];
int lazy_exp[4 * maxn], lazy_shift[4 * maxn];
void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root] = node(left, left);
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);
    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

void push_lazy(int root, int left, int right)
{
    tree[root].lb -= lazy_exp[root];
    tree[root].rb += lazy_exp[root];
    tree[root].lb += lazy_shift[root];
    tree[root].rb += lazy_shift[root];
    if (left != right)
    {
        lazy_exp[2 * root] += lazy_exp[root];
        lazy_exp[2 * root + 1] += lazy_exp[root];
        lazy_shift[2 * root] += lazy_shift[root];
        lazy_shift[2 * root + 1] += lazy_shift[root];
    }

    lazy_exp[root] = lazy_shift[root] = 0;
}

void update_exp(int root, int left, int right, int qleft, int qright, int val)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        lazy_exp[root] += val;
        push_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    update_exp(root * 2, left, mid, qleft, qright, val);
    update_exp(root * 2 + 1, mid + 1, right, qleft, qright, val);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

void update_shift(int root, int left, int right, int qleft, int qright, int val)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        lazy_shift[root] += val;
        push_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    update_shift(root * 2, left, mid, qleft, qright, val);
    update_shift(root * 2 + 1, mid + 1, right, qleft, qright, val);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

node query(int root, int left, int right, int qleft, int qright)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return node();

    if (left >= qleft && right <= qright)
        return tree[root];

    int mid = (left + right) / 2;
    return merge_node(query(root * 2, left, mid, qleft, qright),
                      query(root * 2 + 1, mid + 1, right, qleft, qright));
}

vector < int > occ[maxn];
int val[maxn], pref[maxn];


int sequence(int N, vector<int> A)
{
    A.insert(A.begin(), 0);
    for (int i = 1; i <= N; i ++)
        occ[A[i]].push_back(i);

        build_tree(1, 0, N);
    int ans = 0;
    for (int x = 1; x <= N; x ++)
    {
        for (int i : occ[x - 1])
        {
            update_shift(1, 0, N, i, N, -1);
        }

        for (int i : occ[x])
        {
            update_shift(1, 0, N, i, N, -1);
        }
        /**for (int i = 1; i <= N; i ++)
        {
            if (A[i] < x)
                val[i] = -1;
            else
            if (A[i] == x)
            val[i] = 0;
            else
                val[i] = 1;
            pref[i] = pref[i - 1] + val[i];
        }*/


    int beg = ans + 1;
        for (int i = ans + 1; i < occ[x].size(); i ++)
            update_exp(1, 0, N, occ[x][i], N, 1);
        int i = 0;
        while(i < occ[x].size())
        {
            int j = i + ans;
            if (j >= occ[x].size())
                break;

            ///cout << pref[r] << endl;
            int l = occ[x][i], r = occ[x][j];
            int min_lf = 1e9, max_lf = -1e9;
            int min_rf = 1e9, max_rf = -1e9;
            /**int d = 0;
            for (int p = l - 1; p >= 0; p --)
            {
                if (A[p] == x)
                    d ++;
                min_lf = min(min_lf, pref[p] - d);
                max_lf = max(max_lf, pref[p] + d);
            }
            d = 0;
            for (int p = r; p <= N; p ++)
            {
                if (A[p] == x && p != r)
                    d ++;
                min_rf = min(min_rf, pref[p] - d);
                max_rf = max(max_rf, pref[p] + d);
            }*/
            node lf = query(1, 0, N, 0, l - 1);
            min_lf = lf.lb;
            max_lf = lf.rb;
            node rf = query(1, 0, N, r, N);
            min_rf = rf.lb;
            max_rf = rf.rb;

            max_rf += (j - i + 1);
            min_rf -= (j - i + 1);
            /**cout << "-----------" << endl;
            cout << x << " " << i << " " << j << " " << ans << endl;
            cout << min_lf << " " << max_lf << " " << min_rf << " " << max_rf << endl;
            cout << rf.lb << " : " << rf.rb << endl;*/
            if (max(min_rf, min_lf) <= min(max_rf, max_lf))
            {
                ///cout << x << " " << i << " " << j << endl;
                ans ++;
            }
            else
            {
                update_exp(1, 0, N, 0, l, 1);
                i ++;
            }
            if (j + 1 != occ[x].size())
            update_exp(1, 0, N, occ[x][j + 1], N, -1);
        }
        for (int p = 0; p < i; p ++)
            update_exp(1, 0, N, 0, occ[x][p], -1);

    }
    return ans;
}

Compilation message

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:121:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  121 |     for (int i = 1; i <= N; i ++)
      |     ^~~
sequence.cpp:124:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  124 |         build_tree(1, 0, N);
      |         ^~~~~~~~~~
sequence.cpp:151:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |         for (int i = ans + 1; i < occ[x].size(); i ++)
      |                               ~~^~~~~~~~~~~~~~~
sequence.cpp:154:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |         while(i < occ[x].size())
      |               ~~^~~~~~~~~~~~~~~
sequence.cpp:157:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |             if (j >= occ[x].size())
      |                 ~~^~~~~~~~~~~~~~~~
sequence.cpp:203:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |             if (j + 1 != occ[x].size())
      |                 ~~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:150:9: warning: unused variable 'beg' [-Wunused-variable]
  150 |     int beg = ans + 1;
      |         ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27668 KB Output is correct
2 Correct 12 ms 27604 KB Output is correct
3 Correct 12 ms 27604 KB Output is correct
4 Correct 12 ms 27676 KB Output is correct
5 Correct 17 ms 27672 KB Output is correct
6 Correct 17 ms 27616 KB Output is correct
7 Correct 18 ms 27752 KB Output is correct
8 Correct 18 ms 27752 KB Output is correct
9 Correct 14 ms 27604 KB Output is correct
10 Correct 13 ms 27604 KB Output is correct
11 Correct 12 ms 27724 KB Output is correct
12 Correct 12 ms 27604 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27668 KB Output is correct
2 Correct 12 ms 27604 KB Output is correct
3 Correct 12 ms 27604 KB Output is correct
4 Correct 12 ms 27676 KB Output is correct
5 Correct 17 ms 27672 KB Output is correct
6 Correct 17 ms 27616 KB Output is correct
7 Correct 18 ms 27752 KB Output is correct
8 Correct 18 ms 27752 KB Output is correct
9 Correct 14 ms 27604 KB Output is correct
10 Correct 13 ms 27604 KB Output is correct
11 Correct 12 ms 27724 KB Output is correct
12 Correct 12 ms 27604 KB Output is correct
13 Correct 17 ms 27672 KB Output is correct
14 Correct 14 ms 27700 KB Output is correct
15 Correct 19 ms 27792 KB Output is correct
16 Correct 14 ms 27732 KB Output is correct
17 Correct 19 ms 27708 KB Output is correct
18 Correct 14 ms 27808 KB Output is correct
19 Correct 14 ms 27808 KB Output is correct
20 Correct 14 ms 27732 KB Output is correct
21 Correct 13 ms 27776 KB Output is correct
22 Correct 14 ms 27756 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27668 KB Output is correct
2 Correct 405 ms 49656 KB Output is correct
3 Correct 396 ms 49732 KB Output is correct
4 Correct 610 ms 42272 KB Output is correct
5 Correct 441 ms 48828 KB Output is correct
6 Correct 427 ms 48756 KB Output is correct
7 Correct 412 ms 42260 KB Output is correct
8 Correct 550 ms 42432 KB Output is correct
9 Correct 592 ms 42820 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27604 KB Output is correct
2 Correct 731 ms 44672 KB Output is correct
3 Correct 870 ms 43204 KB Output is correct
4 Correct 918 ms 43200 KB Output is correct
5 Correct 1144 ms 44676 KB Output is correct
6 Correct 1002 ms 43076 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 55392 KB Output is correct
2 Correct 535 ms 55512 KB Output is correct
3 Correct 603 ms 55016 KB Output is correct
4 Correct 554 ms 54892 KB Output is correct
5 Correct 637 ms 51512 KB Output is correct
6 Correct 637 ms 51476 KB Output is correct
7 Correct 613 ms 50264 KB Output is correct
8 Correct 474 ms 49956 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27668 KB Output is correct
2 Correct 12 ms 27604 KB Output is correct
3 Correct 12 ms 27604 KB Output is correct
4 Correct 12 ms 27676 KB Output is correct
5 Correct 17 ms 27672 KB Output is correct
6 Correct 17 ms 27616 KB Output is correct
7 Correct 18 ms 27752 KB Output is correct
8 Correct 18 ms 27752 KB Output is correct
9 Correct 14 ms 27604 KB Output is correct
10 Correct 13 ms 27604 KB Output is correct
11 Correct 12 ms 27724 KB Output is correct
12 Correct 12 ms 27604 KB Output is correct
13 Correct 17 ms 27672 KB Output is correct
14 Correct 14 ms 27700 KB Output is correct
15 Correct 19 ms 27792 KB Output is correct
16 Correct 14 ms 27732 KB Output is correct
17 Correct 19 ms 27708 KB Output is correct
18 Correct 14 ms 27808 KB Output is correct
19 Correct 14 ms 27808 KB Output is correct
20 Correct 14 ms 27732 KB Output is correct
21 Correct 13 ms 27776 KB Output is correct
22 Correct 14 ms 27756 KB Output is correct
23 Correct 94 ms 31896 KB Output is correct
24 Correct 107 ms 31944 KB Output is correct
25 Correct 85 ms 31976 KB Output is correct
26 Correct 132 ms 30940 KB Output is correct
27 Correct 156 ms 31028 KB Output is correct
28 Correct 139 ms 31044 KB Output is correct
29 Correct 141 ms 30772 KB Output is correct
30 Correct 136 ms 30872 KB Output is correct
31 Correct 140 ms 30844 KB Output is correct
32 Correct 70 ms 32780 KB Output is correct
33 Correct 100 ms 31680 KB Output is correct
34 Correct 114 ms 31704 KB Output is correct
35 Correct 94 ms 31684 KB Output is correct
36 Correct 135 ms 31676 KB Output is correct
37 Correct 99 ms 31700 KB Output is correct
38 Correct 122 ms 31720 KB Output is correct

Subtask #7
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27668 KB Output is correct
2 Correct 12 ms 27604 KB Output is correct
3 Correct 12 ms 27604 KB Output is correct
4 Correct 12 ms 27676 KB Output is correct
5 Correct 17 ms 27672 KB Output is correct
6 Correct 17 ms 27616 KB Output is correct
7 Correct 18 ms 27752 KB Output is correct
8 Correct 18 ms 27752 KB Output is correct
9 Correct 14 ms 27604 KB Output is correct
10 Correct 13 ms 27604 KB Output is correct
11 Correct 12 ms 27724 KB Output is correct
12 Correct 12 ms 27604 KB Output is correct
13 Correct 17 ms 27672 KB Output is correct
14 Correct 14 ms 27700 KB Output is correct
15 Correct 19 ms 27792 KB Output is correct
16 Correct 14 ms 27732 KB Output is correct
17 Correct 19 ms 27708 KB Output is correct
18 Correct 14 ms 27808 KB Output is correct
19 Correct 14 ms 27808 KB Output is correct
20 Correct 14 ms 27732 KB Output is correct
21 Correct 13 ms 27776 KB Output is correct
22 Correct 14 ms 27756 KB Output is correct
23 Correct 405 ms 49656 KB Output is correct
24 Correct 396 ms 49732 KB Output is correct
25 Correct 610 ms 42272 KB Output is correct
26 Correct 441 ms 48828 KB Output is correct
27 Correct 427 ms 48756 KB Output is correct
28 Correct 412 ms 42260 KB Output is correct
29 Correct 550 ms 42432 KB Output is correct
30 Correct 592 ms 42820 KB Output is correct
31 Correct 731 ms 44672 KB Output is correct
32 Correct 870 ms 43204 KB Output is correct
33 Correct 918 ms 43200 KB Output is correct
34 Correct 1144 ms 44676 KB Output is correct
35 Correct 1002 ms 43076 KB Output is correct
36 Correct 552 ms 55392 KB Output is correct
37 Correct 535 ms 55512 KB Output is correct
38 Correct 603 ms 55016 KB Output is correct
39 Correct 554 ms 54892 KB Output is correct
40 Correct 637 ms 51512 KB Output is correct
41 Correct 637 ms 51476 KB Output is correct
42 Correct 613 ms 50264 KB Output is correct
43 Correct 474 ms 49956 KB Output is correct
44 Correct 94 ms 31896 KB Output is correct
45 Correct 107 ms 31944 KB Output is correct
46 Correct 85 ms 31976 KB Output is correct
47 Correct 132 ms 30940 KB Output is correct
48 Correct 156 ms 31028 KB Output is correct
49 Correct 139 ms 31044 KB Output is correct
50 Correct 141 ms 30772 KB Output is correct
51 Correct 136 ms 30872 KB Output is correct
52 Correct 140 ms 30844 KB Output is correct
53 Correct 70 ms 32780 KB Output is correct
54 Correct 100 ms 31680 KB Output is correct
55 Correct 114 ms 31704 KB Output is correct
56 Correct 94 ms 31684 KB Output is correct
57 Correct 135 ms 31676 KB Output is correct
58 Correct 99 ms 31700 KB Output is correct
59 Correct 122 ms 31720 KB Output is correct
60 Correct 775 ms 49640 KB Output is correct
61 Correct 810 ms 49732 KB Output is correct
62 Correct 760 ms 49784 KB Output is correct
63 Correct 1066 ms 42944 KB Output is correct
64 Correct 1034 ms 43052 KB Output is correct
65 Correct 1018 ms 42912 KB Output is correct
66 Correct 827 ms 42636 KB Output is correct
67 Correct 879 ms 43148 KB Output is correct
68 Correct 979 ms 43852 KB Output is correct
69 Correct 401 ms 55464 KB Output is correct
70 Correct 696 ms 48936 KB Output is correct
71 Correct 709 ms 48712 KB Output is correct
72 Correct 738 ms 48212 KB Output is correct
73 Correct 811 ms 48404 KB Output is correct
74 Correct 786 ms 48092 KB Output is correct
75 Correct 761 ms 48424 KB Output is correct