Submission #1085247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085247		sunflower	Financial Report (JOI21_financial)	C++14	65 / 100	4062 ms	13304 KiB

Main

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

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define sz(x) ((int) (x).size())
#define all(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

int n, d;

const int maxn = (int) 3e5 + 7;
const int LOG = 18;

int a[maxn + 2], dp[maxn + 2];
int st[maxn + 2][LOG + 1];
int minPos[maxn + 2];

// ----------- SEGMENT TREE ---------------------- //
int seg[4 * maxn + 7];
    void update(int pos, int v) {
        int id = 1, l = 1, r = n;
        while (l < r) {
            int g = (l + r) >> 1;
            if (g >= pos) {
                id = 2 * id;
                r = g;
            } else {
                id = 2 * id + 1;
                l = g + 1;
            }
        }

        maximize(seg[id], v);

        while (id > 1) {
            id >>= 1;
            seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
        }
    }

    int get(int id, int l, int r, int u, int v) {
        if (l > v || u > r) return 0;
        if (u <= l && r <= v) return seg[id];
        int g = (l + r) >> 1;
        return max(get(id << 1, l, g, u, v), get(id << 1 | 1, g + 1, r, u, v));
    }
// ----------- SEGMENT TREE ---------------------- //

namespace subtask1 {
    bool check() {
        return (n <= 20);
    }

    void solve() {
        int ans = 0;
        REP(mask, MASK(n)) {
            if (__builtin_popcount(mask) <= ans) continue;

            vector <int> f;
            bool ok = true;
            REP(i, n) if (BIT(mask, i)) {
                if (f.empty() || i + 1 - f.back() <= d) f.push_back(i + 1);
                else {ok = false; i = n;}
            }

            if (!ok) continue;

            int cnt = 0, ma = 0;
            REP(i, sz(f)) {
                if (maximize(ma, a[f[i]])) cnt++;
            }

            maximize(ans, cnt);
        }

        cout << ans;
    }
};

namespace subtask5 {
    bool check() {
        return (d == n);
    }

    void solve() {
        memset(seg, 0, sizeof(seg));
        FOR(i, 1, n) {
            dp[i] = 1;
            maximize(dp[i], get(1, 1, n, 1, a[i] - 1) + 1);
            update(a[i], dp[i]);
        }

        cout << *max_element(dp + 1, dp + 1 + n);
    }
};

namespace subtask3 {
    bool check() {
        return (n <= 7000);
    }

    void solve() {
        dp[1] = 1;
        FOR(i, 2, n) {
            dp[i] = 1;
            int lst = i;
            FORD(j, i - 1, 1) {
                if (lst - j > d) break;
                if (a[i] > a[j]) maximize(dp[i], dp[j] + 1), lst = j;
            }
        }

        cout << *max_element(dp + 1, dp + 1 + n);
    }
};

namespace subtask4 {
    bool check() {
        return (d == 1);
    }

    void solve() {
        a[0] = -1;
        FOR(i, 1, n) minPos[i] = 0;
        stack <int> st; // greater;
        FOR(i, 1, n) {
            while (!st.empty() && a[st.top()] < a[i]) st.pop();
            if (!st.empty()) minPos[i] = st.top();
            st.push(i);
        }

        dp[1] = 1;
        update(1, 1);
        FOR(i, 2, n) {
            dp[i] = 1;
            if (minPos[i] + 1 <= i - 1) maximize(dp[i], get(1, 1, n, minPos[i] + 1, i - 1) + 1);
            if (a[minPos[i]] == a[i]) maximize(dp[i], dp[minPos[i]]);
            update(i, dp[i]);
        }

        cout << *max_element(dp + 1, dp + 1 + n);
    }
};

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> d;
    vector <int> v;
    FOR(i, 1, n) cin >> a[i], v.push_back(a[i]);
    sort(all(v));
    v.erase(unique(all(v)), v.end());

    FOR(i, 1, n) a[i] = lower_bound(all(v), a[i]) - v.begin() + 1;

    if (subtask4 :: check()) return subtask4 :: solve(), 0;
    if (subtask5 :: check()) return subtask5 :: solve(), 0;
    if (subtask1 :: check()) return subtask1 :: solve(), 0;
    if (subtask3 :: check()) return subtask3 :: solve(), 0;
    subtask3 :: solve();

    return 0;
}

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