제출 #1143756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143756		0pt1mus23	Volontiranje (COCI21_volontiranje)	C++20	0 / 110	0 ms	320 KiB

Main

#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 = 2e5+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) );
    }
};

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

    vector<vector<int>> res;
    vector<int> par(n+23,inf);
    multiset<pair<int,int>> abi; // last el,length
    for(int i=0;i<n+23;i++){
        abi.ins({inf,0});
    }
    if(K>1){
        for(int i = n-1;i>=0;i--){
            int x = arr[i];
            auto it = abi.upper_bound({x,0});
            auto lan = *it;
            abi.erase(it);
            par[arr[i]] = lan.first;  
            lan.first = arr[i];
            lan.second++;
            // cout<<lan.first<<" "<<lan.second<<endl;
            if(lan.second  !=K ){
                abi.ins(lan);
            }
        }
        for(int i = 0;i<n;i++){
            if(par[arr[i]]==inf){
                continue;
            }
            vector<int> lan;
            int u = arr[i];
            while(u!=inf){
                lan.pb(u);
                // cout<<u<<endl;
                u =par[u];
            }
            for(auto v:lan){
                par[v]=inf;
            }
            res.pb(lan);
        }
    }
    else{
        for(int i=1;i<=n;i++){
            res.pb({i});
        }
    }

    vector<int> yer(n+23);
    for(int i=1;i<=n;i++){
        yer[arr[i-1]]=i;
    }
    cout<<res.size()<<" "<<K<<endl;
    for(auto v:res){
        for(auto x:v){
            cout<<yer[x]<<" "; 
        }
        cout<<endl;
    }
}

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

    int tt =1;

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

    return 0;
}

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