Submission #1142199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142199		mnbvcxz123	Volontiranje (COCI21_volontiranje)	C++20	110 / 110	209 ms	98256 KiB

Main

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

constexpr int N=1e6+5;

int n;
int p[N];
int cur[N];
vector<int>dd[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n;
    cur[0]=-N;
    for(int i=1;i<=n;++i){
        cin>>p[i];
        cur[i]=N;
    }
    int lis=0;
    for(int i=1;i<=n;++i){
        int g=lower_bound(cur+1,cur+n+1,p[i])-cur;
        dd[g].push_back(i);
        cur[g]=p[i];
        lis=max(lis,g);
    }
    for(int i=1;i<=lis;++i)
        reverse(dd[i].begin(),dd[i].end());
    vector<vector<int>>ans;
    while(1){
        bool f=0;
        for(int i=1;i<lis;++i){
            if(dd[i].empty() or dd[i+1].empty()){
                f=1;
                break;
            }
            while(!dd[i+1].empty() and dd[i+1].back()<dd[i].back())
                dd[i+1].pop_back();
            if(p[dd[i+1].back()]<p[dd[i].back()]){
                dd[i].pop_back();
                i-=2;
                if(i==-1)i=0;
            }
        }
        if(f)break;
        vector<int>gg;
        for(int i=1;i<=lis;++i){
            if(dd[i].empty()){
                f=1;
                break;
            }
            gg.push_back(dd[i].back());
            dd[i].pop_back();
        }
        if(f)break;
        ans.push_back(gg);
    }
    cout<<ans.size()<<' '<<lis<<'\n';
    for(auto x:ans){
        for(int j:x)cout<<j<<' ';
        cout<<'\n';
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60