oj.uz

Submission #892490

# Submission time Handle Problem Language Result Execution time Memory
892490 2023-12-25T11:58:30 Z quochuy147 Financial Report (JOI21_financial) C++14
17 / 100
 79 ms 36372 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define all(x) (x).begin() , (x).end()
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define file "name"
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}

const int inf = 1e9 + 5;
const ll linf = 1e17;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
const int LOG = 20;

int n, d, res;
int a[N], f[N];
int rmq[N][LOG + 5], lg[N];

void inp()
{
    cin >> n >> d;
    for(int i = 1; i <= n; ++i) cin >> a[i];
}

namespace sub4 {
    void prepare() {
        for(int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;

        for(int i = 1; i <= n; ++i) rmq[i][0] = a[i];
        for(int j = 1; j <= LOG; ++j)
            for(int i = 1; i + MASK(j) - 1 <= n; ++i) rmq[i][j] = max(rmq[i][j - 1], rmq[i + MASK(j - 1)][j - 1]);
    }

    int get(int l, int r) {
        int k = lg[r - l + 1];
        return max(rmq[l][k], rmq[r - MASK(k) + 1][k]);
    }

    void solve() {
        prepare();
        for(int i = n; i >= 1; --i) {
            int l = i + 1, r = n, id = n + 1;
            while(l <= r) {
                int m = (l + r) >> 1;
                if(get(i, m) > a[i]) {
                    id = m;
                    r = m - 1;
                }
                else l = m + 1;
            }
            f[i] = f[id] + 1;
            maximize(res, f[i]);
        }
        cout << res;
    }
}

namespace sub5 {
    int x[N];
    void solve() {
        for(int i = 1; i <= n; ++i) x[i] = inf;
        x[0] = -inf;
        for(int i = 1; i <= n; ++i) {
            int l = 1, r = n, id = 0;
            while(l <= r) {
                int m = (l + r) >> 1;
                if(x[m] >= a[i]) {
                    id = m;
                    r = m - 1;
                }
                else l = m + 1;
            }
            x[id] = a[i];
            maximize(res, id);
        }
        cout << res;
    }
}

namespace sub3 {
    void solve() {
        a[0] = -1;
        for(int i = 1; i <= n; ++i) f[i] = 1;
        for(int i = 1; i < n; ++i) {
            int id = i;
            maximize(res, f[i]);
            id += d;
            for(int j = i + 1; j <= n; ++j) {
                if(a[j] > a[i] && j - i <= d) maximize(f[j], f[i] + 1);
                if(a[j] <= a[i]) {
                    id = j + d;
                    continue;
                }
                if(j > id) break;
                maximize(f[j], f[i] + 1);
            }
        }
        cout << res;
    }
}

void solve()
{
    if(d == 1) return void(sub4::solve());
    if(d == n) return void(sub5::solve());
    if(n <= 7000) return void(sub3::solve());
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
//	freopen(file".inp" , "r" , stdin);
//	freopen(file".out" , "w" , stdout);
    inp();
    solve();
    return 0;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 20.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 36184 KB Output is correct
2 Correct 71 ms 35876 KB Output is correct
3 Correct 71 ms 36216 KB Output is correct
4 Correct 69 ms 36180 KB Output is correct
5 Correct 70 ms 36220 KB Output is correct
6 Correct 70 ms 36184 KB Output is correct
7 Correct 79 ms 36196 KB Output is correct
8 Correct 69 ms 36188 KB Output is correct
9 Correct 69 ms 36180 KB Output is correct
10 Correct 69 ms 36184 KB Output is correct
11 Correct 68 ms 36228 KB Output is correct
12 Correct 70 ms 36372 KB Output is correct
13 Correct 65 ms 36176 KB Output is correct
14 Correct 68 ms 36180 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8792 KB Output is correct
2 Correct 39 ms 8592 KB Output is correct
3 Correct 47 ms 8512 KB Output is correct
4 Correct 42 ms 8516 KB Output is correct
5 Correct 44 ms 8532 KB Output is correct
6 Correct 42 ms 8540 KB Output is correct
7 Correct 38 ms 8536 KB Output is correct
8 Correct 28 ms 8628 KB Output is correct
9 Correct 37 ms 8660 KB Output is correct
10 Correct 42 ms 8648 KB Output is correct
11 Correct 44 ms 8604 KB Output is correct
12 Correct 29 ms 8796 KB Output is correct

Subtask #6
0 / 35.0

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