Submission #703809

#	Time	Username	Problem	Language	Result	Execution time	Memory
703809		weakweakweak	Volontiranje (COCI21_volontiranje)	C++14	0 / 110	566 ms	524288 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define fs first
#define sc second
#define pii pair<int,int>

const int N=1010000;
int a[N], fr[N], n, lb[N];
vector<int>lis={INT_MAX}, v;
vector<pii> lv[N];
vector<vector<int>>ans;
set<int>st[N];
bool dead[N]={0};

#pragma GCC optimize("Ofast")

bool dfs(int i, int t){
    if(dead[i])return 0;
    v.push_back(i);
    if(t==1)return 1;
    auto it=st[t-1].lower_bound(lb[i]), it2=st[t-1].lower_bound(i);
    if(it==it2||it==st[t-1].end()){
        dead[i]=1;
        return 0;
    }
    vector<int>err;
    while(it!=it2){
        if(dfs(*it, t-1)){
           // for(int x:err)st[t-1].erase(x);
            return 1;}
        err.push_back(*it);
        it=it++;
    }
    for(int x:err)st[t-1].erase(x);
    v.pop_back();
    dead[i]=1;
    return 0;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        auto it=lower_bound(lis.begin(), lis.end(), a[i]);
        if(it==lis.end())lis.push_back(a[i]), fr[i]=lis.size();
        else lis[it-lis.begin()]=a[i], fr[i]=it-lis.begin()+1;
        st[fr[i]].insert(i); lv[fr[i]].push_back({a[i],i});
        if(fr[i]==1)continue;
        int l=0, r=lv[fr[i]-1].size()-1;
        while(l<r){
            int mid=(l+r)/2;
            if(lv[fr[i]-1][mid].fs < a[i])r=mid;
            else l=mid+1;
        }
        lb[i]=min(lv[fr[i]-1][l].sc,i);
    }

    for(auto i:st[lis.size()]){
        v.resize(0);
        if(dfs(i, lis.size())){
            if(v.size()!=lis.size())continue;
            reverse(v.begin(), v.end());
            ans.push_back(v);
            for(int i=0; i<v.size()-1; i++)st[i+1].erase(v[i]);
        }
    }

    cout << ans.size() << ' ' << lis.size() << '\n';
    for(auto v:ans){
        for(int x:v)cout << x << ' ';
        cout << '\n';
    }
return 0;}

/*
1 1 2 1 1 3 2 2 3 2 3 1 3 2 3
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for(int i=0; i<v.size()-1; i++)st[i+1].erase(v[i]);
      |                          ~^~~~~~~~~~~

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