oj.uz

Submission #892534

# Submission time Handle Problem Language Result Execution time Memory
892534 2023-12-25T13:19:46 Z quochuy147 Financial Report (JOI21_financial) C++14
5 / 100
 488 ms 41988 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];

bool cmp(const pii &a, const pii &b) {
    if(a.fi == b.fi) return a.se > b.se;
    return a.fi < b.fi;
}

namespace sub6 {
    void solve() {
        for(int i = 1; i <= n; ++i) b[i] = mp(a[i], i);
        sort(b + 1, b + n + 1, cmp);
        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 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 3 ms 14680 KB Output is correct
9 Correct 3 ms 12972 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Correct 2 ms 14684 KB Output is correct
15 Correct 2 ms 12636 KB Output is correct
16 Incorrect 3 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 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 3 ms 14680 KB Output is correct
9 Correct 3 ms 12972 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Correct 2 ms 14684 KB Output is correct
15 Correct 2 ms 12636 KB Output is correct
16 Incorrect 3 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 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 3 ms 14680 KB Output is correct
9 Correct 3 ms 12972 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Correct 2 ms 14684 KB Output is correct
15 Correct 2 ms 12636 KB Output is correct
16 Incorrect 3 ms 12636 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 41988 KB Output is correct
2 Correct 307 ms 38472 KB Output is correct
3 Incorrect 380 ms 37456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 27860 KB Output is correct
2 Correct 224 ms 25820 KB Output is correct
3 Correct 333 ms 25864 KB Output is correct
4 Correct 480 ms 38868 KB Output is correct
5 Correct 447 ms 38848 KB Output is correct
6 Correct 488 ms 38940 KB Output is correct
7 Correct 240 ms 40900 KB Output is correct
8 Correct 236 ms 38848 KB Output is correct
9 Correct 244 ms 38844 KB Output is correct
10 Correct 355 ms 38712 KB Output is correct
11 Correct 462 ms 38832 KB Output is correct
12 Correct 449 ms 38712 KB Output is correct

Subtask #6
0 / 35.0

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