제출 #1185619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185619		dosts	Volontiranje (COCI21_volontiranje)	C++20	10 / 110	0 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());
    vi newb;
    vi match(n+1,0);
    for (int i=l;i>=1;i--) {
        sort(all(buckets[i]));
        reverse(all(buckets[i]));
        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(buckets[i-1].back());
                buckets[i-1].pop_back();
            }
        }
        buckets[i-1] = newb;
        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);
        }
    }
    cout << ans.size() sp l << endl;
    for (auto it : ans) {
        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: 10 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 60