Submission #876072

#	Time	Username	Problem	Language	Result	Execution time	Memory
876072		green_gold_dog	Financial Report (JOI21_financial)	C++17	100 / 100	974 ms	51200 KiB

Main

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
        if (b > a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
bool assign_min(T& a, T b) {
        if (b < a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
T square(T a) {
        return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
        ll operator() (pair<ll, ll> p) const {
                return ((__int128)p.first * MOD + p.second) % INF64;
        }
};

struct segment_tree {
        vector<ll> tree;
        ll size;
        segment_tree(ll n) {
                size = 1;
                while (size < n) {
                        size *= 2;
                }
                tree.resize(size * 2, 0);
        }
        void set(ll x, ll y) {
                set(1, 0, size, x, y);
        }
        void set(ll v, ll l, ll r, ll x, ll y) {
                if (x < l || r <= x) {
                        return;
                }
                if (r - l == 1) {
                        tree[v] = y;
                        return;
                }
                ll mid = (l + r) / 2;
                set(v * 2, l, mid, x, y);
                set(v * 2 + 1, mid, r, x, y);
                tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
        }
        ll get(ll l, ll r) {
                return get(1, 0, size, l, r);
        }
        ll get(ll v, ll l, ll r, ll ql, ll qr) {
                if (ql <= l && r <= qr) {
                        return tree[v];
                }
                if (qr <= l || r <= ql) {
                        return 0;
                }
                ll mid = (l + r) / 2;
                return max(get(v * 2, l, mid, ql, qr), get(v * 2 + 1, mid, r, ql, qr));
        }
        ll last(ll l, ll r, ll x) {
                return last(1, 0, size, l, r, x);
        }
        ll last(ll v, ll l, ll r, ll ql, ll qr, ll x) {
                if (r - l == 1) {
                        return l;
                }
                ll mid = (l + r) / 2;
                if (get(v * 2 + 1, mid, r, ql, qr) > x) {
                        return last(v * 2 + 1, mid, r, ql, qr, x);
                } else {
                        return last(v * 2, l, mid, ql, qr, x);
                }
        }
};

struct segment_tree2 {
        vector<ll> tree, m;
        ll size;
        segment_tree2(ll n) {
                size = 1;
                while (size < n) {
                        size *= 2;
                }
                tree.resize(size * 2, 0);
                m.resize(size * 2, 0);
        }
        void push(ll v) {
                assign_max(m[v * 2], m[v]);
                assign_max(tree[v * 2], m[v]);
                assign_max(m[v * 2 + 1], m[v]);
                assign_max(tree[v * 2 + 1], m[v]);
                m[v] = 0;
        }
        ll get(ll x) {
                return get(1, 0, size, x);
        }
        ll get(ll v, ll l, ll r, ll x) {
                if (x < l || r <= x) {
                        return 0;
                }
                if (r - l == 1) {
                        return tree[v];
                }
                push(v);
                ll mid = (l + r) / 2;
                return max(get(v * 2, l, mid, x), get(v * 2 + 1, mid, r, x));
        }
        void add(ll l, ll r, ll x) {
                add(1, 0, size, l, r, x);
        }
        void add(ll v, ll l, ll r, ll ql, ll qr, ll x) {
                if (ql <= l && r <= qr) {
                        assign_max(tree[v], x);
                        assign_max(m[v], x);
                        return;
                }
                if (qr <= l || r <= ql) {
                        return;
                }
                push(v);
                ll mid = (l + r) / 2;
                add(v * 2, l, mid, ql, qr, x);
                add(v * 2 + 1, mid, r, ql, qr, x);
        }
};

void solve() {
        ll n, d;
        cin >> n >> d;
        vector<ll> arr(n);
        vector<pair<ll, ll>> all;
        for (ll i = 0; i < n; i++) {
                cin >> arr[i];
                all.emplace_back(arr[i], -i);
        }
        segment_tree2 dp(n);
        segment_tree st(n);
        set<ll> be;
        for (ll i = 0; i < n; i++) {
                st.set(i, 1);
                be.insert(i);
                dp.add(i, i + 1, 1);
        }
        sort(all.rbegin(), all.rend());
        ll ans = 0;
        for (auto[_, i] : all) {
                i = -i;
                ll ndp = dp.get(i);
                assign_max(ans, ndp);
                ll cu = st.last(0, i + 1, d);
                dp.add(cu, i, ndp + 1);
                auto it = be.find(i);
                it++;
                if (it != be.end()) {
                        ll x = st.get(i, i + 1) + st.get(*it, *it + 1);
                        st.set(*it, x);
                }
                st.set(i, 0);
                be.erase(i);
        }
        cout << ans << '\n';
}

int main() {
        if (IS_FILE) {
                freopen("", "r", stdin);
                freopen("", "w", stdout);
        }
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        ll t = 1;
        if (IS_TEST_CASES) {
                cin >> t;
        }
        for (ll i = 0; i < t; i++) {
                solve();
        }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:195:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  195 |                 freopen("", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:196:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  196 |                 freopen("", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~

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