Submission #864222

#	Time	Username	Problem	Language	Result	Execution time	Memory
864222		vjudge1	Financial Report (JOI21_financial)	C++17	100 / 100	492 ms	16976 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int MAXN=3e5, K=(1<<19);

int n, d;
int a[MAXN];
set<pair<int, int> > segments, bad;
int tree[2*K-1]={0};

bool compare(int x, int y)
{
    if (a[x]==a[y])
        return x<y;

    return a[x]>a[y];
}

void updatesegments(int x)
{
    auto itr=segments.lower_bound({x, 1e9});
    auto itl=itr;
    bool left=false;
    if (itr!=segments.begin())
    {
        itl--;
        left=true;
    }
    if (left && itr!=segments.end() && x==(*itl).second+1 && x==(*itr).first-1)
    {
        pair<int, int> newsegment={(*itl).first, (*itr).second};
        auto oldleft=*itl;
        auto oldright=*itr;
        segments.erase(oldleft);
        segments.erase(oldright);
        segments.insert(newsegment);
        bad.erase(oldleft);
        bad.erase(oldright);
        if (newsegment.second-newsegment.first+1>=d)
            bad.insert(newsegment);
    }
    else if (left && x==(*itl).second+1 && x==(*itl).second+1)
    {
        pair<int, int> newsegment={(*itl).first, (*itl).second+1};
        auto oldleft=*itl;
        segments.erase(oldleft);
        segments.insert(newsegment);
        bad.erase(oldleft);
        if (newsegment.second-newsegment.first+1>=d)
            bad.insert(newsegment);
    }
    else if (itr!=segments.end() && x==(*itr).first-1)
    {
        pair<int, int> newsegment={(*itr).first-1, (*itr).second};
        auto oldright=*itr;
        segments.erase(oldright);
        segments.insert(newsegment);
        bad.erase(oldright);
        if (newsegment.second-newsegment.first+1>=d)
            bad.insert(newsegment);
    }
    else
    {
        segments.insert({x, x});
        if (d==1)
            bad.insert({x, x});
    }

    return;
}

int find(int x, int l, int r, int lt, int rt)
{
    if (l>=rt || r<=lt)
        return 0;
    if (l>=lt && r<=rt)
        return tree[x];

    return max(find(2*x+1, l, (l+r)/2, lt, rt), find(2*x+2, (l+r)/2, r, lt, rt));
}

void update(int x, int l, int r, int index, int value)
{
    if (l>index || r<=index)
        return;
    tree[x]=max(tree[x], value);
    if (r-l==1)
        return;
    update(2*x+1, l, (l+r)/2, index, value);
    update(2*x+2, (l+r)/2, r, index, value);

    return;
}

int main()
{
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);

    cin >> n >> d;
    int processorder[n], farthest[n];
    int maxscore=0;
    for (int i=0; i<n; i++)
        cin >> a[i];
    for (int i=0; i<n; i++)
        processorder[i]=i;
    sort(processorder, processorder+n, compare);
    farthest[processorder[0]]=n-1;
    for (int i=1; i<n; i++)
    {
        updatesegments(processorder[i-1]);
        int x=processorder[i];
        auto it=bad.lower_bound({x, -1});
        if (it==bad.end())
        {
            farthest[x]=n-1;
            continue;
        }
        if ((*it).first<=x && (*it).second>=x && x+d<=(*it).second)
        {
            farthest[x]=x+d;
            continue;
        }
        if ((*it).first<=x && (*it).second>=x)
            it++;
        if (it==bad.end())
            farthest[x]=n-1;
        else
            farthest[x]=(*it).first-1+d;
    }
    for (int i=0; i<n; i++)
    {
        int x=processorder[i];
        int score=find(0, 0, K, x, farthest[x]+1)+1;
        update(0, 0, K, x, score);
        maxscore=max(maxscore, score);
    }
    cout << maxscore;

    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