oj.uz

Submission #876061

# Submission time Handle Problem Language Result Execution time Memory
876061 2023-11-21T07:51:23 Z green_gold_dog Financial Report (JOI21_financial) C++17
0 / 100
 4000 ms 35372 KB 
//#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, l, mid, ql, qr) > x) {
                        return last(v * 2 + 1, mid, r, ql, qr, x);
                } else {
                        return last(v * 2, l, mid, 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);
        }
        vector<ll> dp(n, 1);
        segment_tree st(n);
        set<ll> be;
        for (ll i = 0; i < n; i++) {
                st.set(i, 1);
                be.insert(i);
        }
        sort(all.rbegin(), all.rend());
        ll ans = 0;
        for (auto[_, i] : all) {
                i = -i;
                assign_max(ans, dp[i]);
                ll cu = max(0ll, st.last(0, i + 1, d) - 1);
                for (ll j = cu; j < i; j++) {
                        assign_max(dp[j], dp[i] + 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

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 468 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 468 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 468 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4014 ms 35232 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4029 ms 35372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 468 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -