Submission #1228781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228781		meth_enjoyer	Financial Report (JOI21_financial)	C++20	31 / 100	78 ms	5820 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int maxN = 3e5 + 5;
int n, d;
int a[maxN];
vector<int> val;

namespace sub1{

    int get(int mask){
        int res = 0, pre = 0, m = 0;
        for (int i = 1; i <= n; ++i)
        if (mask >> (i - 1) & 1){
            if (!pre)
                res++;
            else
            {
                if (i - pre <= d)
                    res+= (a[i] > m);
            }

            m = max(m, a[i]);
            pre = i;
        }

        return res;
    }

    void solve(){
        int ans = 0;
        for (int mask = 0; mask < (1 << n); ++mask)
            ans = max(ans, get(mask));

        cout << ans;

    }
}

void compress(){
    sort(val.begin(), val.end());
    val.resize(unique(val.begin(), val.end()) - val.begin());
    for (int i = 1; i <= n; ++i)
        a[i] = upper_bound(val.begin(), val.end(), a[i]) - val.begin();
}

namespace sub4{
    vector<int> q;

    void solve(){
        compress();
        int ans = 0;

        for (int i = n; i > 0; --i){
            while (q.size() && a[q.back()] <= a[i])
                q.pop_back();

            ans = max(ans, (int) q.size() + 1);

            q.push_back(i);
        }

        cout << ans;
    }
}

namespace sub5{
    int f[maxN];

    int get(int x){
        int res = 0;
        for (; x > 0; x-= x & (-x))
            res = max(res, f[x]);
        return res;
    }

    void update(int x, int val){
        for (; x <= maxN - 5; x+= x & (-x))
            f[x] = max(f[x], val);
    }

    void solve(){
        compress();
        int ans = 0;
        for (int i = 1; i <= n; ++i){
            int res = get(a[i] - 1) + 1;
            ans = max(ans, res);
            update(a[i], res);
        }

        cout << ans;
    }
}

void solve(){
    if (n <= 20)
        sub1::solve();
    else
    {
        if (d == 1)
            sub4::solve();
        if (d == n)
            sub5::solve();
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    // freopen("a.inp", "r", stdin);
    // freopen("a.out", "w", stdout);
    cin >> n >> d;
    for (int i = 1; i <= n; ++i)
        cin >> a[i], val.push_back(a[i]);
    solve();
    return 0;
}

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