Submission #854698

#	Time	Username	Problem	Language	Result	Execution time	Memory
854698		kderylo	Financial Report (JOI21_financial)	C++17	100 / 100	391 ms	41556 KiB

Main

#include <iostream>
#include <set>
#include <vector>
#include <map>
using namespace std;
const int stala=524288;
set<pair<int,int> >s; //war poz
vector<int>w[stala];
set<int>intervals;
int tab[stala];
int mapka[stala];
int range[stala];
int tree[2*stala];
int tree2[stala];
void remove_element(int index,int d)
{
    auto it=intervals.upper_bound(index);
    if(it==intervals.begin()){
        return;
    }
    it--;
    int pocz=*it;
    int kon=mapka[pocz];
    if(pocz<=index&&index<=kon){
        intervals.erase(it);
        int x1=pocz;
        int y1=index-1;
        int x2=index+1;
        int y2=kon;
        if(y1-x1+1>=d){
            intervals.insert(x1);
            mapka[x1]=y1;
        }
        if(y2-x2+1>=d){
            intervals.insert(x2);
            mapka[x2]=y2;
        }
    }
}
int find_range(int index,int ile,int d)
{
    auto it=intervals.upper_bound(index);
    if(it==intervals.end()){
        return ile;
    }
    return *it+d-1;
}
void update(int ind,int ind2,int war,int tr[])
{
    ind+=stala-1;
    ind2+=stala-1;
    tr[ind]=max(tr[ind],war);
    tr[ind2]=max(tr[ind2],war);
    while(ind/2!=ind2/2){
        if(ind%2==0){
            tr[ind+1]=max(tr[ind+1],war);
        }
        if(ind2%2==1){
            tr[ind2-1]=max(tr[ind2-1],war);
        }
        ind/=2;
        ind2/=2;
    }
}
int query(int ind,int tr[])
{
    ind+=stala-1;
    int wyn=0;
    while(ind>0){
        wyn=max(wyn,tr[ind]);
        ind/=2;
    }
    return wyn;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ile,d;
    cin>>ile>>d;
    for(int i=1;i<=ile;i++){
        int a;
        cin>>a;
        tab[i]=a;
        s.insert({a,i});
    }
    int pop=-1;
    int ind=0;
    while(!s.empty()){
        auto it=s.begin();
        int war=it->first;
        int poz=it->second;
        s.erase(it);
        if(war!=pop){
            pop=war;
            ind++;
        }
        w[ind].push_back(poz);
    }
    intervals.insert(1);
    mapka[1]=ile;
    for(int i=1;i<=ind;i++){
        for(int j=0;j<(int)w[i].size();j++){
            remove_element(w[i][j],d);
        }
        for(int j=0;j<(int)w[i].size();j++){
            range[w[i][j]]=find_range(w[i][j],ile,d);
        }
    }
    for(int i=1;i<=ind;i++){
        for(int j=0;j<(int)w[i].size();j++){
            int wyn=query(w[i][j],tree);
            tree2[w[i][j]]=wyn+1;
        }
        for(int j=0;j<(int)w[i].size();j++){
            int wyn=tree2[w[i][j]];
            if(w[i][j]+1<=range[w[i][j]]){
                update(w[i][j]+1,range[w[i][j]],wyn,tree);
            }
        }
    }
    int res=tree2[ile];
    for(int i=1;i<=ile-1;i++){
        if(tab[i]>=tab[ile]&&range[i]==ile){
            res=max(res,tree2[i]);
        }
    }
    cout<<res;
    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