Submission #534328

#	Time	Username	Problem	Language	Result	Execution time	Memory
534328		Monarchuwu	Financial Report (JOI21_financial)	C++17	65 / 100	2718 ms	532292 KiB

Main

#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>
using namespace std;
typedef long long ll;

const int N = 3e5 + 7, N3 = 7000 + 3;
int n, d;
int a[N];

int b[N];
void compress() {
    copy(a + 1, a + n + 1, b + 1);
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
}

// dp[i][j] -> dp[k][max(j, a[k])]
// j <  a[k] : dp[k][a[k]] <- dp[i][j] + 1
//          => dp[k][a[k]] <- max(dp[i][a[k] - 1], ..., dp[i][0]) + 1
// j >= a[k] : dp[k][  j ] <- dp[i][j]
void maximize(int &a, int b) { if (a < b) a = b; }
int dp[N3][N3], prf[N3][N3];
deque<int> dq[2][N3];
void subtask3() {
    for (int j = 0; j <= n; ++j) {
        dq[0][j].push_back(0);
        dq[1][j].push_back(0);
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (dq[0][j].front() < i - d) dq[0][j].pop_front();
            if (dq[1][j].front() < i - d) dq[1][j].pop_front();
        }

        if (!dq[0][a[i] - 1].empty())
            dp[i][a[i]] = prf[dq[0][a[i] - 1].front()][a[i] - 1] + 1;

        for (int j = a[i]; j <= n; ++j)
            if (!dq[1][j].empty())
                maximize(dp[i][j], dp[dq[1][j].front()][j]);

        int maxprf(0);
        for (int j = 0; j <= n; ++j) {
            prf[i][j] = maxprf = max(maxprf, dp[i][j]);

            while (!dq[0][j].empty() && prf[dq[0][j].back()][j] < prf[i][j]) dq[0][j].pop_back();
            while (!dq[1][j].empty() && dp[dq[1][j].back()][j] < dp[i][j]) dq[1][j].pop_back();
            dq[0][j].push_back(i);
            dq[1][j].push_back(i);
        }
    }

    cout << prf[n][n] << '\n';
}

int L[N], cnt[N];
int st[N], top;
void subtask4() {
    for (int i = 1; i <= n; ++i) {
        while (top && a[st[top]] < a[i]) --top;
        ++cnt[L[i] = st[top]];
        st[++top] = i;
    }

    int ans(0), sum(1);
    for (int i = 0; i < n; ++i) {
        sum += cnt[i] - 1;
        ans = max(ans, sum);
    }
    cout << ans << '\n';
}

int lis[N];
void subtask5() {
    int cnt(0);
    for (int i = 1, p; i <= n; ++i) {
        p = lower_bound(lis + 1, lis + cnt + 1, a[i]) - lis;
        if (p > cnt) ++cnt;
        lis[p] = a[i];
    }
    cout << cnt << '\n';
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> d;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    compress();

    if (n <= 7000) subtask3();
    else if (d == 1) subtask4();
    else if (d == n) subtask5();
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35