oj.uz

Submission #892382

# Submission time Handle Problem Language Result Execution time Memory
892382 2023-12-25T09:48:15 Z quochuy147 Financial Report (JOI21_financial) C++14
17 / 100
 77 ms 36252 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];
}

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]);
}

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] = 0;
        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 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] = min(rmq[i][j - 1], rmq[i + MASK(j - 1)][j - 1]);
    }

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

    void solve() {
        prepare();
        for(int i = 1; i <= n; ++i) {
            f[i] = 1;
            if(a[i] > a[i - 1]) f[i] = f[i - 1] + 1;
            for(int j = 1; j < i - 1; ++j) {
                if(a[j] >= a[i]) continue;
                int l = max(1, i - d), r = min(i, j + d);
                if(l <= r && get(l, r) <= a[j]) maximize(f[i], f[j] + 1);
            }
            maximize(res, f[i]);
        }
        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 4444 KB Output is correct
2 Correct 1 ms 4444 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 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Incorrect 1 ms 4444 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 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 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Incorrect 1 ms 4444 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 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 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Incorrect 1 ms 4444 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 34904 KB Output is correct
2 Correct 72 ms 34652 KB Output is correct
3 Correct 77 ms 36216 KB Output is correct
4 Correct 70 ms 36188 KB Output is correct
5 Correct 68 ms 36188 KB Output is correct
6 Correct 70 ms 36188 KB Output is correct
7 Correct 65 ms 36180 KB Output is correct
8 Correct 70 ms 36180 KB Output is correct
9 Correct 68 ms 36176 KB Output is correct
10 Correct 74 ms 36180 KB Output is correct
11 Correct 70 ms 36176 KB Output is correct
12 Correct 74 ms 36172 KB Output is correct
13 Correct 72 ms 36252 KB Output is correct
14 Correct 69 ms 36216 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7512 KB Output is correct
2 Correct 37 ms 7504 KB Output is correct
3 Correct 42 ms 7504 KB Output is correct
4 Correct 41 ms 7516 KB Output is correct
5 Correct 44 ms 7512 KB Output is correct
6 Correct 41 ms 7560 KB Output is correct
7 Correct 38 ms 7516 KB Output is correct
8 Correct 27 ms 7508 KB Output is correct
9 Correct 36 ms 7296 KB Output is correct
10 Correct 42 ms 7548 KB Output is correct
11 Correct 41 ms 7508 KB Output is correct
12 Correct 27 ms 7508 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 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 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Incorrect 1 ms 4444 KB Output isn't correct
17 Halted 0 ms 0 KB -