Submission #936835

#	Time	Username	Problem	Language	Result	Execution time	Memory
936835		ace5	Financial Report (JOI21_financial)	C++17	100 / 100	662 ms	40460 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

vector<int> segTree;
vector<int> dp;
vector<int> otr;
vector<int> a;
set<int> pos;
int n,d;

void modify(int i,int x,int l,int r,int indV)
{
    if(l > i || r < i)
        return ;
    else if(l == r)
    {
        segTree[indV] = x;
        return ;
    }
    int m = (l+r)/2;
    modify(i,x,l,m,indV*2+1);
    modify(i,x,m+1,r,indV*2+2);
    segTree[indV] = max(segTree[indV*2+1],segTree[indV*2+2]);
    return ;
}
int get1(int lx,int rx,int l,int r,int indV)
{
    if(l > rx || r < lx)
        return -1;
    else if(l >= lx && r <= rx)
    {
        if(l == r)
        {
            return (segTree[indV] == 1 ? l : -1);
        }
        else
        {
            if(segTree[indV] == 0)
            {
                return -1;
            }
            int m = (l+r)/2;
            int t = get1(lx,rx,l,m,indV*2+1);
            if(t != -1)
            {
                return t;
            }
            else
            {
                return get1(lx,rx,m+1,r,indV*2+2);
            }
        }
    }
    int m = (l+r)/2;
    int t = get1(lx,rx,l,m,indV*2+1);
    if(t != -1)
        return t;
    else
        return get1(lx,rx,m+1,r,indV*2+2);
}
int get2(int lx,int rx,int l,int r,int indV)
{
    if(l > rx || r < lx)
        return 0;
    else if(l >= lx && r <= rx)
        return segTree[indV];
    int m = (l+r)/2;
    int sl = get2(lx,rx,l,m,indV*2+1);
    int sr = get2(lx,rx,m+1,r,indV*2+2);
    return max(sl,sr);
}
void ins(int x)
{
    pos.insert(x);
    auto it = pos.find(x);
    if(it != pos.begin())
    {
        it--;
        if(x-(*it) <= d)
        {
            modify(*it,0,0,n-1,0);
        }
        else
        {
            modify(*it,1,0,n-1,0);
        }
        it++;
    }
    it++;
    if(it == pos.end())
    {
        modify(x,1,0,n-1,0);
    }
    else
    {
        if((*it)-x <= d)
        {
            modify(x,0,0,n-1,0);
        }
        else
            modify(x,1,0,n-1,0);
    }
    return ;
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> d;
    a.resize(n);
    segTree.resize(4*n);
    dp.resize(n);
    otr.resize(n);
    vector<pair<int,int>> b;
    for(int i = 0;i < n;++i)
    {
        cin >> a[i];
        b.push_back({a[i],i});
    }
    sort(b.begin(),b.end());
    for(int i = 0;i < n;++i)
    {
        int lj = i;
        for(int j = i;j < n;++j)
        {
            if(b[j].first != b[i].first)
            {
                break;
            }
            lj = j;
            ins(b[j].second);
        }
        for(int j = i;j < n;++j)
        {
            if(b[j].first != b[i].first)
            {
                break;
            }
            otr[b[j].second] = min(n-1,get1(b[j].second,n-1,0,n-1,0)+d);
        }
        i = lj;
    }
    segTree.clear();
    segTree.resize(4*n);
    sort(b.rbegin(),b.rend());
    int ans = 0;
    for(int i = 0;i < n;++i)
    {
        int lj = i;
        for(int j = i;j < n;++j)
        {
            if(b[j].first != b[i].first)
            {
                break;
            }
            lj = j;
            dp[b[j].second] = get2(b[j].second+1,otr[b[j].second],0,n-1,0)+1;
            ans = max(ans,dp[b[j].second]);
        }
        for(int j = i;j < n;++j)
        {
            if(b[j].first != b[i].first)
            {
                break;
            }
            modify(b[j].second,dp[b[j].second],0,n-1,0);
        }
        i = lj;
    }
    cout << ans << "\n";
    return 0;
}

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