oj.uz

Submission #1084151

# Submission time Handle Problem Language Result Execution time Memory
1084151 2024-09-05T11:45:37 Z yoav_s Financial Report (JOI21_financial) C++17
5 / 100
 418 ms 103508 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> p;
typedef pair<ll, p> tri;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<p> vp;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<vv> vvv;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef vector<vvvp> vvvvp;

#define double long double
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;

const ll mod = 1e9 + 7;
const ll INF = 1e18;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define loop(a) for (ll i = 0; i < a; i++)
#define setmin(a, b) a = min(a, b)
#define setmax(a, b) a = max(a, b)
#define all(v) v.begin(), v.end()

void update(v &st, ll i, ll val)
{
    ll n = st.size() / 2;
    i += n;
    st[i] = val;
    i /= 2;
    while (i > 0)
    {
        st[i] = min(st[2 * i], st[2 * i + 1]);
        i /= 2;
    }
}

ll query(v &st, ll l, ll r)
{
    ll n=  st.size() / 2;
    l += n; r += n;
    ll res = INF;
    while (l <= r)
    {
        if (l % 2 == 1)
        {
            res = min(res, st[l]);
            l++;
        }
        if (r % 2 == 0)
        {
            res = min(res, st[r]);
            r--;
        }
        l /= 2; r /= 2;
    }
    return res;
}

ll lastSmaller(v &st, ll x)
{
    ll i = 1;
    ll n = st.size() / 2;
    if (st[1] >= x) return -1;
    while (i < n)
    {
        if (st[2 * i + 1] < x) i = 2 * i + 1;
        else i *= 2;
    }
    return i - n;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    ll N, D;
    cin >> N >> D;
    v A(N);
    for (ll i =0; i < N; i++) cin >> A[i];
    multiset<ll> vals;
    v mini(N, -1);
    for (ll i = 0; i < N; i++)
    {
        vals.insert(A[i]);
        mini[i] = *vals.begin();
        if (i >= D) vals.erase(vals.find(A[i - D]));
    }
    v expire(N, -1);
    multiset<p> curVals;
    for (ll i = 0; i < N; i++)
    {
        curVals.emplace(A[i], i);
        while ((*curVals.begin()).f < mini[i])
        {
            expire[(*curVals.begin()).s] = i;
            curVals.erase(curVals.begin());
        }
    }
    vv expiringIn(N);
    for (ll i =0; i < N; i++) if (expire[i] != -1) expiringIn[expire[i]].pb(i);
    ll n = pow(2, ceil(log2(N + 1)));
    v st(2 * n, INF);
    update(st, 0, -INF);
    vector<multiset<ll>> endings(N + 1);
    endings[0].insert(-INF);
    for (ll i = 1; i <= N; i++) endings[i].insert(INF);
    v res(N, -1);
    ll best = 0;
    for (ll  i = 0; i < N; i++)
    {
        ll add = lastSmaller(st, A[i]);
        if (add != -1)
        {
            endings[add + 1].insert(A[i]);
            best = max(best, add + 1);
            update(st, add + 1, *endings[add + 1].begin());
            res[i] = add + 1;
        }
        for (ll x : expiringIn[i])
        {
            if (res[x] == -1) continue;
            endings[res[x]].erase(endings[res[x]].find(A[x]));
            update(st, res[x], *endings[res[x]].begin());
        }
    }
    cout << best << "\n";
    return 0;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 88936 KB Output is correct
2 Correct 183 ms 64344 KB Output is correct
3 Incorrect 172 ms 61268 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 255 ms 103508 KB Output is correct
2 Correct 329 ms 102996 KB Output is correct
3 Correct 418 ms 102996 KB Output is correct
4 Correct 383 ms 103016 KB Output is correct
5 Correct 299 ms 103020 KB Output is correct
6 Correct 360 ms 102992 KB Output is correct
7 Correct 215 ms 102996 KB Output is correct
8 Correct 240 ms 102992 KB Output is correct
9 Correct 182 ms 102484 KB Output is correct
10 Correct 269 ms 102644 KB Output is correct
11 Correct 377 ms 102996 KB Output is correct
12 Correct 274 ms 102992 KB Output is correct

Subtask #6
0 / 35.0

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