Submission #1084151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084151		yoav_s	Financial Report (JOI21_financial)	C++17	5 / 100	418 ms	103508 KiB

Main

#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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35