Submission #703639

#	Time	Username	Problem	Language	Result	Execution time	Memory
703639		Pacybwoah	Volontiranje (COCI21_volontiranje)	C++14	110 / 110	309 ms	92336 KiB

Main

//upsolve
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
vector<int> bit;
int n;
void modify(int x,int pos){
    while(pos<=n){
        bit[pos]=max(bit[pos],x);
        pos+=(pos&-pos);
    }
}
int query(int pos){
    int ans=0;
    while(pos>0){
        ans=max(ans,bit[pos]);
        pos-=(pos&-pos);
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    bit.resize(n+1);
    vector<int> vec(n);
    for(int i=0;i<n;i++) cin>>vec[i];
    vector<int> dp(n);
    int maxi=0;
    for(int i=0;i<n;i++){
        dp[i]=query(vec[i])+1;
        maxi=max(maxi,dp[i]);
        modify(dp[i],vec[i]);
    }
    vector<vector<int>> l(maxi+1);
    for(int i=0;i<n;i++) l[dp[i]].push_back(i);
    for(int i=1;i<=maxi;i++) reverse(l[i].begin(),l[i].end());
    vector<vector<int>> ans;
    vector<int> st;
    while(1){
        int k=st.size();
        if(k==0){
            if(l[1].empty()) break;
            st.push_back(l[1].back());
            l[1].pop_back();
        }
        else if(k==maxi){
            ans.push_back(st);
            st.clear();
        }
        else{
            while(!l[k+1].empty()&&l[k+1].back()<st.back()) l[k+1].pop_back();
            if(!l[k+1].empty()&&vec[st.back()]<vec[l[k+1].back()]){
                st.push_back(l[k+1].back());
                l[k+1].pop_back();
            }
            else{
                st.pop_back();
            }
        }
    }
    cout<<ans.size()<<" "<<maxi<<"\n";
    for(auto x:ans){
        for(auto y:x) cout<<y+1<<" ";
        cout<<"\n";
    }
}

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