Submission #1311576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311576		bbartek	Financial Report (JOI21_financial)	C++20	100 / 100	469 ms	58412 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define st first
#define nd second
#define pb push_back

const int maxn = 3e5+7;

int tab[maxn];
int minn[maxn];
int koniec[maxn];
unordered_map<int,int> mapa;
int drzewo[2048*1024];
int n2=1;

void update(int v,int x){
    v += n2-1;
    drzewo[v] = max(drzewo[v],x);
    if(x==0)
        drzewo[v] = 0;
    v/=2;
    while(v!=0){
        drzewo[v] = max(drzewo[v*2],drzewo[v*2+1]);
        v/=2;
    }
}

int query(int v,int l,int r,int a,int b){
    if(a>b)
        return 0;
    if(a <= l && r <= b){
        return drzewo[v];
    }
    else if(a > r || b < l){
        return 0;
    }
    else{
        int mid = (l+r)/2;
        return max(query(v*2,l,mid,a,b),query(v*2+1,mid+1,r,a,b));
    }
}

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

    int n,k;
    cin>>n>>k;

    set<int> rozne;
    for(int i=1;i<=n;i++){
        cin>>tab[i];
        rozne.insert(tab[i]);
    }
    //cout<<"jestem\n";

    int licz = 0;
    for(auto it : rozne){
        licz++;
        mapa[it] = licz;
    }

    multiset<int> minima;
    for(int i=n;i>n-k;i--){
        minima.insert(tab[i]);
    }
    for(int i=n-k;i>=1;i--){
        minima.insert(tab[i]);
        auto it = minima.find(tab[i+k]);
        minima.erase(it);
        minn[i+k] = mapa[*(minima.begin())];
    }

    while(n2<n)
        n2*=2;

    set<int> drzewne;
    int x,wyn=0;
    for(int i=1;i<=n;i++){
        if(i >= k){
            while(drzewne.size() != 0){
                auto it = drzewne.begin();
                if((*it) >= minn[i])
                    break;
                update((*it),0);
                drzewne.erase(it);
            }
        }
        x = query(1,1,n2,1,mapa[tab[i]]-1)+1;
        wyn = max(wyn,x);
        update(mapa[tab[i]],x);
        drzewne.insert(mapa[tab[i]]);
    }

    cout<<wyn<<"\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