oj.uz

Submission #892530

# Submission time Handle Problem Language Result Execution time Memory
892530 2023-12-25T13:14:50 Z quochuy147 Financial Report (JOI21_financial) C++14
17 / 100
 86 ms 42724 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], lim[N];
int rmq[N][LOG + 5], lg[N];
pii b[N];
set <pii> s;
map <int, int> x;
vector <int> pos[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 + d;
            maximize(res, f[i]);
            for(int j = i + 1; j <= n; ++j) {
                if(a[j] <= a[i]) {
                    id = j + d;
                    continue;
                }
                maximize(f[j], f[i] + 1);
                if(j >= id) break;
            }
        }
        cout << res;
    }
}

struct segtree {
    int st[4 * N];

    segtree() {}

    void update(int id, int l, int r, int i, int v) {
        if(i < l || r < i) return ;
        if(l == r) return void(st[id] = v);
        int m = (l + r) >> 1;
        update(id << 1, l, m, i, v);
        update(id << 1 | 1, m + 1, r, i, v);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }

    int walk_left(int id, int l, int r, int v) {
        if(r < v || st[id] == 0) return n + 1;
        if(l == r) return l;
        int m = (l + r) >> 1;
        int res = walk_left(id << 1, l, m, v);
        if(res == n + 1) res = walk_left(id << 1 | 1, m + 1, r, v);
        return res;
    }

    int walk_right(int id, int l, int r, int v) {
        if(v < l || st[id] == 0) return 0;
        if(l == r) return l;
        int m = (l + r) >> 1;
        int res = walk_right(id << 1 | 1, m + 1, r, v);
        if(!res) res = walk_right(id << 1, l, m, v);
        return res;
    }

    int get(int id, int l, int r, int u, int v) {
        if(v < l || r < u) return 0;
        if(l >= u && r <= v) return st[id];
        int m = (l + r) >> 1;
        return max(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
    }

} st[2];

namespace sub6 {
    void solve() {
        for(int i = 1; i <= n; ++i) b[i] = mp(a[i], i);
        sort(b + 1, b + n + 1);
        s.insert({1, n - 1});
        for(int i = 1; i <= n; ++i) {
            int id = b[i].se;
            st[0].update(1, 1, n, id, 1);
            int l = st[0].walk_right(1, 1, n, id - 1), r = st[0].walk_left(1, 1, n, id + 1);
            l++; r--;
            s.erase({l, r - l});
            if(id - l > d) s.insert({l, id - l});
            if(r - id > d) s.insert({id, r - id});
            auto it = s.lower_bound({id, 0});
            if(it == s.end()) lim[id] = n;
            else lim[id] = min(n, (*it).fi + d);
        }

        for(int i = 1; i <= n; ++i) {
            for(int p : pos[i]) st[1].update(1, 1, n, p, 0);
            int id = lower_bound(b + 1, b + n + 1, mp(a[i], 0)) - b;
            f[i] = st[1].get(1, 1, n, 1, id - 1) + 1;
            id += x[a[i]];
            x[a[i]]++;
            st[1].update(1, 1, n, id, f[i]);
            pos[lim[i] + 1].pb(id);
            maximize(res, f[i]);
        }
        cout << res;
    }
}

void solve()
{
//    if(n <= 7000) return void(sub3::solve());
    if(d == 1) return void(sub4::solve());
    if(d == n) return void(sub5::solve());
    sub6::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 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12792 KB Output is correct
6 Correct 2 ms 12736 KB Output is correct
7 Correct 2 ms 12632 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 3 ms 12632 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12776 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Correct 2 ms 14936 KB Output is correct
15 Correct 3 ms 12684 KB Output is correct
16 Incorrect 2 ms 12636 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12792 KB Output is correct
6 Correct 2 ms 12736 KB Output is correct
7 Correct 2 ms 12632 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 3 ms 12632 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12776 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Correct 2 ms 14936 KB Output is correct
15 Correct 3 ms 12684 KB Output is correct
16 Incorrect 2 ms 12636 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12792 KB Output is correct
6 Correct 2 ms 12736 KB Output is correct
7 Correct 2 ms 12632 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 3 ms 12632 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12776 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Correct 2 ms 14936 KB Output is correct
15 Correct 3 ms 12684 KB Output is correct
16 Incorrect 2 ms 12636 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 67 ms 42700 KB Output is correct
2 Correct 74 ms 42724 KB Output is correct
3 Correct 75 ms 42588 KB Output is correct
4 Correct 72 ms 42588 KB Output is correct
5 Correct 69 ms 42708 KB Output is correct
6 Correct 86 ms 42460 KB Output is correct
7 Correct 65 ms 42580 KB Output is correct
8 Correct 69 ms 42580 KB Output is correct
9 Correct 68 ms 42580 KB Output is correct
10 Correct 68 ms 42580 KB Output is correct
11 Correct 69 ms 42580 KB Output is correct
12 Correct 72 ms 42588 KB Output is correct
13 Correct 84 ms 42696 KB Output is correct
14 Correct 69 ms 42716 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13144 KB Output is correct
2 Correct 38 ms 13136 KB Output is correct
3 Correct 48 ms 13088 KB Output is correct
4 Correct 41 ms 13148 KB Output is correct
5 Correct 45 ms 13136 KB Output is correct
6 Correct 42 ms 13148 KB Output is correct
7 Correct 38 ms 13092 KB Output is correct
8 Correct 28 ms 13148 KB Output is correct
9 Correct 37 ms 13016 KB Output is correct
10 Correct 39 ms 13148 KB Output is correct
11 Correct 40 ms 13148 KB Output is correct
12 Correct 28 ms 13148 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12792 KB Output is correct
6 Correct 2 ms 12736 KB Output is correct
7 Correct 2 ms 12632 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 3 ms 12632 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12776 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Correct 2 ms 14936 KB Output is correct
15 Correct 3 ms 12684 KB Output is correct
16 Incorrect 2 ms 12636 KB Output isn't correct
17 Halted 0 ms 0 KB -