Submission #1264714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264714		chinhhoang	Volontiranje (COCI21_volontiranje)	C++20	10 / 110	12 ms	23880 KiB

Main

#include <bits/stdc++.h>
using namespace std;
vector<int> lis[1000004];
bool vi[1009040];
int dp[1003303];
struct Fenwick_tree{
    vector<int>fen;
    int n;
    void init(int _n){
        n=_n;
        fen.assign(n+5,0);
    }
    void add(int i,int val){
        while(i<=n){
            fen[i]=max(fen[i],val);
            i += i&-i;
        }
    }
    int get(int i){
        int s=0;
        while(i)s=max(s,fen[i]),i&=i-1;
        return s;
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);
    int n;
    cin >> n;
    int a[n];
    int i,j;
    Fenwick_tree ft;
    ft.init(n + 5);
    i = -1; while(++i < n) cin >> a[i];
    bool ok = 1;
    i = -1; while(++i < n - 1) if(a[i] < a[i+1]) ok = 0;
    if(ok){
        cout << n << ' ' << 1 <<'\n';
        i = -1; while(++i < n ) cout << i + 1 << '\n';
        return 0;
    }
    int max_lis = 0;
    i = -1;while(++i < n){
        dp[i] = ft.get(a[i] - 1) + 1;
        ft.add(a[i], dp[i]);
        max_lis = max(max_lis, dp[i]);
        lis[dp[i]].push_back(i);
    }
    i = 0; while(i++ < n) if(i&1) reverse(lis[i].begin(),lis[i].end());
    vector<vector<int>>ans;
    while(true){
        bool ok = 1;
        int st = -1;
        i = -1;while(++i < n) if(dp[i] == max_lis && vi[i] == 0) st = i;
        if(st == -1) break;
        vector<int> res;
        vi[st] = 1;
        res.push_back(st);
        while(dp[st] > 1){
            
        bool can_find = 0;
            for(auto v:lis[dp[st] - 1]) {
                if(!vi[v] && a[v] < a[st] && v < st){
                    st = v;
                    res.push_back(v);
                    can_find = 1;
                    break;
                }
            }
            if(can_find==0)break;;
        }
        
        if(res.size() == max_lis) {
            reverse(res.begin(), res.end());
            ans.push_back(res);
            for(auto v : res) vi[v] = 1;
        }
    }
    cout << ans.size() << ' '<< max_lis << '\n';
    for(auto v:ans){
        for(auto it : v) cout <<  it +1 << ' ';
        cout << '\n';
    }
    return 0;
}
    

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