Submission #1091623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091623		raphaelp	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	136 ms	262144 KiB

subsequence

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

void maxegal(pair<int, int> &a, pair<int, int> b)
{
    a = max(a, b);
}

class SegTree
{
private:
    vector<vector<vector<pair<int, pair<int, int>>>>> st;
    int N;
    int l(int x) { return (x << 1); }
    int r(int x) { return (x << 1) + 1; }
    void compact(vector<vector<pair<int, pair<int, int>>>> &Tab)
    {
        for (int i = 0; i < 20; i++)
        {
            sort(Tab[i].begin(), Tab[i].end());
            vector<pair<int, pair<int, int>>> temp;
            for (int j = 0; j < Tab[i].size(); j++)
            {
                if (j > 0 && Tab[i][j].first == Tab[i][j - 1].first)
                    temp.back() = max(temp.back(), Tab[i][j]);
                else
                    temp.push_back(Tab[i][j]);
            }
            swap(temp, Tab[i]);
        }
    }
    pair<int, int> Query(int L, int R, int a, int b, int x)
    {
        compact(st[x]);
        if (L == R)
            return ((st[x][b].empty()) ? (pair<int, int>){0, 0} : st[x][b][0].second);
        for (int j = 0; j < 20; j++)
        {
            for (auto i : st[x][j])
            {
                st[l(x)][j].push_back({i.first / 2, i.second});
                st[r(x)][j + i.first % 2].push_back({i.first / 2, i.second});
            }
            st[x][j].clear();
        }
        int m = (L + R) / 2;
        if (a % 2)
            return Query(m + 1, R, a / 2, b, r(x));
        else
            return Query(L, m, a / 2, b, l(x));
    }

public:
    SegTree(int x)
    {
        N = (1 << (int)ceil(log2(x)));
        st.assign(2 * N, {});
        for (int i = 0; i < 2 * N; i++)
            st[i].assign(20, {});
    }
    void update(int a, int val, int i)
    {
        st[1][0].push_back({a, {val, i}});
    }
    pair<int, int> Query(int a, int b)
    {
        return Query(0, N - 1, a, b, 1);
    }
};

int main()
{
    int N;
    cin >> N;
    vector<int> A(N), K(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    for (int i = 0; i < N; i++)
    {
        cin >> K[i];
    }
    SegTree ST(1000000);
    vector<pair<int, int>> dp(N);
    int maxx = 0;
    for (int i = 0; i < N; i++)
    {
        dp[i] = ST.Query(A[i], K[i]);
        dp[i].first++;
        ST.update(A[i], dp[i].first, i);
        if (dp[i].first > dp[maxx].first)
            maxx = i;
    }
    cout << dp[maxx].first << '\n';
    vector<int> ans(dp[maxx].first);
    for (int i = dp[maxx].first - 1; i >= 0; i--)
    {
        ans[i] = maxx + 1;
        maxx = dp[maxx].second;
    }
    for (auto val : ans)
        cout << val << ' ';
    return 0;
}

Compilation message (stderr)

subsequence.cpp: In member function 'void SegTree::compact(std::vector<std::vector<std::pair<int, std::pair<int, int> > > >&)':
subsequence.cpp:22:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |             for (int j = 0; j < Tab[i].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60