Submission #1143821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143821		0pt1mus23	Volontiranje (COCI21_volontiranje)	C++20	110 / 110	373 ms	133552 KiB

Main

// NOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
// NASIL AKLIMA GELMEDI!!!!!!!!!
// NEDEN DAHA FAZLA DUSUNMEDIM!! *SARCASM COMMENT
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert
#define pb  push_back
#define endl '\n' 
#define all(x) x.begin(),x.end()

const int mod = 998244353;
const int inf = LLONG_MAX;
const int LG  = 23;
const int sze = 1e6+23;

struct segtree{
    vector<int> T;
    segtree(int n){
        T.resize(4*n,0);
    }
    void upd(int node,int idx,int l,int r,int v){
        if(l==r){
            T[node]=v;
            return;
        }
        int mid = (l+r)/2;
        if(idx<=mid) upd(2*node,idx,l,mid,v);
        else upd(2*node +1,idx,mid+1,r,v);

        T[node]=max(T[node*2],T[node *2+1]);
    }
    int qry(int node,int l,int r,int lx,int rx){
        if(lx>r || rx<l) return 0;
        if(lx>=l && rx<=r) return T[node];
        return max( qry(2*node,l,r,lx,(lx+rx)/2), qry(2*node +1,l,r,(lx+rx)/2 +1, rx) );
    }
};
vector<int> cand[sze];
int mndx[sze];

void fast(){
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    segtree st(n+23);
    int K = 1;

    for(int i=0;i<n;i++){
        int x = st.qry(1,0,arr[i]-1,1,n)+1;
        K = max(K,x);
        st.upd(1,arr[i],1,n,x);
        cand[x].pb(i);
    }

    bool flag=true;

    vector<vector<int>> res;
    vector<int> curr;
    curr.pb(cand[1][0]);
    int len =1;
    while(!curr.empty() && flag){
        if(len==K){
            res.pb(curr);
            for(int i =1;i<=K;i++){
                if((++mndx[i])==cand[i].size()){
                    flag=false;
                    break;
                }
            }
            len=1;
            curr.clear();
            curr.pb(cand[1][mndx[1]]);
        }
        else{
            while(mndx[len + 1]< cand[len+1].size() && cand[len+1][mndx[len+1]]< cand[len][mndx[len]]){
                ++mndx[len+1];
            }
            if(mndx[len+1]==cand[len+1].size()){
                break;
            }
            if(arr[curr.back()]< arr[cand[len+1][mndx[len+1]]]){
                curr.pb(cand[++len][mndx[len]]);
            }
            else{
                if( (++mndx[len]) ==cand[len].size()){
                    break;
                }
                --len;
                curr.pop_back();
                if(curr.empty()){
                    len=1;
                    curr.pb(cand[len][mndx[len]]);
                }
            }
        }
    }
    cout<<res.size()<<" "<<K<<endl;
    for(auto v:res){
        for(auto x:v){
            cout<<x+1<<" ";
        }
        cout<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt =1;

    // cin>>tt;
    while(tt--){
        fast();
    }

    return 0;
}

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