Submission #523539

#	Time	Username	Problem	Language	Result	Execution time	Memory
523539		Deepesson	Financial Report (JOI21_financial)	C++17	100 / 100	2278 ms	128036 KiB

Main

#include <bits/stdc++.h>
#define MAX 305000
int ttab[MAX*4];
void tadd(int t,int x,int la=0,int ra=MAX-1,int pos=1){
    if(t>ra||la>t)return;
    ttab[pos]=std::max(ttab[pos],x);
    if(la==ra)return;
    int m = (la+ra)/2;
    tadd(t,x,la,m,pos*2);
    tadd(t,x,m+1,ra,(pos*2)+1);
}
int tget(int l,int r,int la=0,int ra=MAX-1,int pos=1){
    if(l>ra||la>r)return 0;
    if(la>=l&&ra<=r){
        return ttab[pos];
    }
    int m = (la+ra)/2;
    return std::max(tget(l,r,la,m,pos*2),tget(l,r,m+1,ra,(pos*2)+1));
}
int array[MAX];
int N,D;
typedef std::pair<int,int> pii;
typedef std::pair<int,int*> pipo;
std::priority_queue<pii> tab[MAX*4];
void add(int t,pii x,int la=0,int ra=MAX-1,int pos=1){
    if(t>ra||la>t)return;
    tab[pos].push(x);
    if(la==ra)return;
    int m = (la+ra)/2;
    add(t,x,la,m,pos*2);
    add(t,x,m+1,ra,(pos*2)+1);
}
pii get(int l,int r,int la=0,int ra=MAX-1,int pos=1){
    if(l>ra||la>r)return {0,0};
    if(la>=l&&ra<=r){
        while(tab[pos].size()){
            int x = tab[pos].top().second;
            int valor = array[x];
            int permite = tget(x,MAX-1);
            if(valor<permite){
                tab[pos].pop();
                continue;
            }
            return tab[pos].top();
        }
        return {0,0};
    }
    int m = (la+ra)/2;
    return std::max(get(l,r,la,m,pos*2),get(l,r,m+1,ra,(pos*2)+1));
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>N>>D;
    std::vector<pipo> vec;
    for(int i=0;i!=N;++i){
        auto& x = array[i];
        std::cin>>x;
        vec.push_back({x,&x});
    }
    std::sort(vec.begin(),vec.end());
    {
        int cur=1;
        int last=-1;
        for(auto&x:vec){
            if(x.first!=last){
                last=x.first;
                ++cur;
            }
            *x.second=cur;
        }
    }
    std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
    int ans=0;
    for(int i=0;i!=N;++i){
        queue.push({array[i],i});
        int permite = i-D;
        while(queue.top().second<=permite)queue.pop();
        int x = array[i];
        int prev = get(0,x-1).first;
        int resultado = prev+1;
        ans=std::max(ans,resultado);
        add(x,{resultado,i});
        tadd(i,queue.top().first);
    }
    std::cout<<ans<<"\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