oj.uz

Submission #959432

# Submission time Handle Problem Language Result Execution time Memory
959432 2024-04-08T08:05:48 Z Alkaser_ID Financial Report (JOI21_financial) C++17
5 / 100
 145 ms 21496 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];
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;
    for (ll i = 0; i < n; ++i) {
        a[v[i].i] = i + 1;
    }
    ll res = 0; ++MX;
    for (ll i = n; i > 0; --i) {
        if (i + d < n) 
            del(1, 1, MX, a[i + d + 1]);
        ll x = get(1, 1, MX, a[i], MX);
        ++x;
        res = max(res, x);
        update(1, 1, MX, a[i], x);
    }
    cout << res;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2524 KB Output is correct
9 Correct 1 ms 2512 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 2 ms 2516 KB Output is correct
12 Correct 1 ms 2516 KB Output is correct
13 Correct 1 ms 2400 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Incorrect 1 ms 2396 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2524 KB Output is correct
9 Correct 1 ms 2512 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 2 ms 2516 KB Output is correct
12 Correct 1 ms 2516 KB Output is correct
13 Correct 1 ms 2400 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Incorrect 1 ms 2396 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2524 KB Output is correct
9 Correct 1 ms 2512 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 2 ms 2516 KB Output is correct
12 Correct 1 ms 2516 KB Output is correct
13 Correct 1 ms 2400 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Incorrect 1 ms 2396 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 20596 KB Output is correct
2 Incorrect 145 ms 20524 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 84 ms 20148 KB Output is correct
2 Correct 139 ms 19824 KB Output is correct
3 Correct 145 ms 21320 KB Output is correct
4 Correct 131 ms 21168 KB Output is correct
5 Correct 127 ms 21496 KB Output is correct
6 Correct 135 ms 20920 KB Output is correct
7 Correct 88 ms 21128 KB Output is correct
8 Correct 83 ms 20408 KB Output is correct
9 Correct 89 ms 20012 KB Output is correct
10 Correct 117 ms 19664 KB Output is correct
11 Correct 127 ms 21408 KB Output is correct
12 Correct 112 ms 20664 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2524 KB Output is correct
9 Correct 1 ms 2512 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 2 ms 2516 KB Output is correct
12 Correct 1 ms 2516 KB Output is correct
13 Correct 1 ms 2400 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Incorrect 1 ms 2396 KB Output isn't correct
16 Halted 0 ms 0 KB -