Submission #1182892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182892		AlgorithmWarrior	Financial Report (JOI21_financial)	C++20	100 / 100	353 ms	10392 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int const MAX=300005;
int n,d;

struct AINT{
    int v[4*MAX];
    void update(int nod,int st,int dr,int poz,int val){
        if(st==dr)
            v[nod]=val;
        else{
            int mij=(st+dr)/2;
            if(poz<=mij)
                update(2*nod,st,mij,poz,val);
            else
                update(2*nod+1,mij+1,dr,poz,val);
            v[nod]=max(v[2*nod],v[2*nod+1]);
        }
    }
    int query(int nod,int st,int dr,int a,int b){
        if(a<=st && dr<=b)
            return v[nod];
        int rasp=0;
        int mij=(st+dr)/2;
        if(a<=mij)
            rasp=max(rasp,query(2*nod,st,mij,a,b));
        if(b>mij)
            rasp=max(rasp,query(2*nod+1,mij+1,dr,a,b));
        return rasp;
    }
}aint;

map<int,int>intv;

void add_pos(int pos){
    auto it=intv.upper_bound(pos);
    if(it!=intv.begin()){
        it=prev(it);
        if(pos<=it->second)
            return;
    }
    intv[pos]=pos;
    it=intv.lower_bound(pos);
    if(it!=intv.begin()){
        it=prev(it);
        if(pos-it->second<=d){
            it->second=pos;
            it=next(it);
            intv.erase(it);
        }
    }
    it=intv.upper_bound(pos);
    if(it!=intv.end()){
        if(it->first-pos<=d){
            int capat=it->second;
            it=prev(it);
            it->second=capat;
            it=next(it);
            intv.erase(it);
        }
    }
}

struct valpoz{
    int val,poz;
    bool operator<(valpoz ot){
        if(val!=ot.val)
            return val<ot.val;
        return poz>ot.poz;
    }
}v[MAX];

void read(){
    cin>>n>>d;
    int i;
    for(i=1;i<=n;++i){
        cin>>v[i].val;
        v[i].poz=i;
    }
    sort(v+1,v+n+1);
}

int final_ans;

void solve(){
    int i;
    for(i=1;i<=n;++i){
        add_pos(v[i].poz);
        auto it=intv.upper_bound(v[i].poz);
        it=prev(it);
        int ans=aint.query(1,1,n,it->first,v[i].poz)+1;
        if(it->second==n && final_ans<ans)
            final_ans=ans;
        aint.update(1,1,n,v[i].poz,ans);
    }
}

int main()
{
    read();
    solve();
    cout<<final_ans;
    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