oj.uz

Submission #959537

# Submission time Handle Problem Language Result Execution time Memory
959537 2024-04-08T12:14:24 Z Alkaser_ID Financial Report (JOI21_financial) C++17
5 / 100
 448 ms 39920 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
// second mod 998244353
const ll N = 3e5 + 5;

ll a[N], b[N], ind[N];
struct order
{
    ll i, v;
};
bool cmp(order x, order y) {
    if (x.v == y.v) return x.i > y.i;
    return x.v < y.v;
}
ll seg[10 * N];
inline void update(ll node, ll l, ll r, ll ind, ll vl) {
    if (l == r) return void(seg[node] = vl);
    ll mid = (l + r) / 2;
    if (ind <= mid)
        update(node * 2, l, mid, ind, vl);
    else update(node * 2 + 1, mid + 1, r, ind, vl);
    seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
}
inline void del(ll node, ll l, ll r, ll ind) {
    if (l == r) return void(seg[node] = 0);
    ll mid = (l + r) / 2;
    if (ind <= mid)
        del(node * 2, l, mid, ind);
    else del(node * 2 + 1, mid + 1, r, ind);
    seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
}
inline ll get(ll node, ll l, ll r, ll lx, ll rx) {
    if (l >= lx && r <= rx) return seg[node];
    if (l > rx || r < lx) return 0;
    ll mid = (l + r) / 2;
    ll r1 = get(node * 2, l, mid, lx, rx);
    ll r2 = get(node * 2 + 1, mid + 1, r, lx, rx);
    return max(r1, r2);
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n, d; cin >> n >> d;
    vector<order> v;
    for (ll i = 1; i <= n; ++i) {
        cin >> a[i];
        order nw;
        nw.v = a[i]; nw.i = i;
        v.push_back(nw);
    }
    sort(v.begin(), v.end(), cmp);
    ll MX = n + 2;
    map<ll, ll> en;
    for (ll i = 0; i < n; ++i) {
        if (i > 0) {
            if (v[i].v != v[i - 1].v) en[v[i - 1].v] = i;
        }
        ind[v[i].i] = i + 1;
    }
    en[v[n - 1].v] = n;
    ll res = 0; ++MX;
    for (ll i = n; i > 0; --i) {
        if (i + d < n)
            del(1, 1, MX, ind[i + d + 1]);
        ll x = get(1, 1, MX, en[a[i]] + 1, MX);
        ++x;
        res = max(res, x);
        update(1, 1, MX, ind[i], x);
    }
    cout << res;
}


/*
7 3
0 1 2 2 1 2 3

*/

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 464 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 348 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 444 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 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 464 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 348 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 444 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 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 464 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 348 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 444 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 20912 KB Output is correct
2 Incorrect 122 ms 20560 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 21208 KB Output is correct
2 Correct 116 ms 20896 KB Output is correct
3 Correct 169 ms 21028 KB Output is correct
4 Correct 448 ms 39636 KB Output is correct
5 Correct 333 ms 39728 KB Output is correct
6 Correct 443 ms 39612 KB Output is correct
7 Correct 158 ms 39604 KB Output is correct
8 Correct 157 ms 39608 KB Output is correct
9 Correct 167 ms 39460 KB Output is correct
10 Correct 229 ms 39544 KB Output is correct
11 Correct 420 ms 39732 KB Output is correct
12 Correct 344 ms 39920 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 464 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 348 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 444 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -