Submission #1091603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091603		raphaelp	Longest beautiful sequence (IZhO17_subsequence)	C++14	7 / 100	62 ms	99248 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<map<int, pair<int, int>>> st;
    int N;
    int l(int x) { return (x << 1); }
    int r(int x) { return (x << 1) + 1; }
    pair<int, int> Query(int L, int R, int a, int b, int x)
    {
        if (L == R)
            return st[x][b];
        for (auto i : st[x])
        {
            int val = i.first / 100, nb = i.first % 100;
            maxegal(st[l(x)][(val / 2) * 100 + nb], {i.second});
            maxegal(st[r(x)][val / 2 * 100 + nb + val % 2], i.second);
        }
        st[x].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, {});
    }
    void update(int a, int val, int i, int f)
    {
        if (f <= 15)
            maxegal(st[1][a * 100], {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, N);
        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 << ' ';
}

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