Submission #699077

#	Time	Username	Problem	Language	Result	Execution time	Memory
699077		Hanksburger	Financial Report (JOI21_financial)	C++17	100 / 100	738 ms	23916 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int seg[1200005], dp[300005];
pair<int, int> a[300005];
set<pair<int, int> > s;
set<int> t;
bool cmp(pair<int, int> x, pair<int, int> y)
{
    if (x.first!=y.first)
        return x.first>y.first;
    return x.second<y.second;
}
void upd(int i, int l, int r, int x, int y)
{
    if (l==r)
    {
        seg[i]=y;
        return;
    }
    int mid=(l+r)/2;
    if (x<=mid)
        upd(i*2, l, mid, x, y);
    else
        upd(i*2+1, mid+1, r, x, y);
    seg[i]=max(seg[i*2], seg[i*2+1]);
}
int qry(int i, int l, int r, int ql, int qr)
{
    if (ql<=l && r<=qr)
        return seg[i];
    int mid=(l+r)/2, mx=0;
    if (l<=qr && ql<=mid)
        mx=max(mx, qry(i*2, l, mid, ql, qr));
    if (mid+1<=qr && ql<=r)
        mx=max(mx, qry(i*2+1, mid+1, r, ql, qr));
    return mx;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i=1; i<=n; i++)
    {
        cin >> a[i].first;
        a[i].second=i;
    }
    sort(a+1, a+n+1, cmp);
    for (int i=1; i<=n; i++)
    {
        int ind=a[i].second, ind2;
        auto it=s.lower_bound({ind, ind});
        if (it!=s.end() && ind+1==(*it).first)
        {
            int l=(*it).first, r=(*it).second;
            s.erase({l, r});
            it=s.insert({ind, r}).first;
            if (ind+m-1<=r)
                t.insert(ind+m-1);
            if (it!=s.begin() && ind-1==(*prev(it)).second)
            {
                int L=(*prev(it)).first, R=(*prev(it)).second;
                s.erase({ind, r});
                s.erase({L, R});
                it=s.insert({L, r}).first;
                for (int j=max(L+m-1, ind); j<=min(ind+m-2, r); j++)
                    t.insert(j);
            }
        }
        else if (it!=s.begin() && ind-1==(*prev(it)).second)
        {
            int L=(*prev(it)).first, R=(*prev(it)).second;
            s.erase({L, R});
            it=s.insert({L, ind}).first;
            if (L+m-1<=ind)
                t.insert(ind);
        }
        else
        {
            s.insert({ind, ind});
            if (m==1)
                t.insert(ind);
        }
        if (t.lower_bound(ind+m)==t.end())
            ind2=n;
        else
            ind2=*t.lower_bound(ind+m);
        upd(1, 1, n, ind, qry(1, 1, n, ind+1, ind2)+1);
    }
    cout << qry(1, 1, n, 1, n);
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35