제출 #1185679

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

Main

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sp << " " << 
using namespace std;

const int N = 3e5+10,MOD = 1e9+7,inf = 2e12;


struct FT {
    vi bit;
    int n;

    void put(int p,int v) {
        for (int i = p;i<=n;i+=i&-i) bit[i]=max(bit[i],v);
    }
    int get(int p) {
        int ans = 0;
        for (int i = p;i>0;i-=i&-i) ans=max(ans,bit[i]);
        return ans;
    }

    FT(int nn) {
        n = nn;
        bit.assign(n+1,0);
    }
};

void solve() {
    int n;
    cin >> n;
    vi a(n+1);
    vector<vi> ans;
    for (int i=1;i<=n;i++) cin >> a[i];
    vi dp(n+1,0);
    FT ft(n);
    for (int i=1;i<=n;i++) {
        dp[i] = ft.get(a[i])+1;
        ft.put(a[i],dp[i]);
    }
    vi buckets[n+1];
    for (int i=1;i<=n;i++) buckets[dp[i]].push_back(i);
    int l = *max_element(dp.begin()+1,dp.end());
    dp.assign(n+1,0);
    vi newb;
    vi match(n+1,0);
    for (int i=1;i<=l;i++) {
        sort(all(buckets[i]));
        reverse(all(buckets[i]));
        if (i > 1) {
            for (auto it : buckets[i]) {
                while (!buckets[i-1].empty() && buckets[i-1].back() >= it) buckets[i-1].pop_back();
                if (!buckets[i-1].empty() && a[buckets[i-1].back()] >= a[it]) continue;
                if (!buckets[i-1].empty()) {
                    match[it] = buckets[i-1].back();
                    newb.push_back(it);
                    buckets[i-1].pop_back();
                }
            }
        }
        else {
            newb = buckets[1];
        }
        buckets[i] = newb;
        sort(all(buckets[i]));
        newb.clear();
    } 
    for (int i=1;i<=n;i++) dp[i] = dp[match[i]]+1;
    for (int i=1;i<=n;i++) {
        if (dp[i] == l) {
            int pos = i;
            vi nw;
            nw.push_back(pos);
            while (match[pos]) {
                pos = match[pos];
                nw.push_back(pos);
            }
            reverse(all(nw));
            ans.push_back(nw);
        }
    }
    reverse(all(ans));
    cout << ans.size() sp l << endl;
    for (auto it : ans) {
        assert(it.size() == l);
        for (auto itt : it) cout << itt << ' ';
        cout << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
} 

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