Submission #703773

#	Time	Username	Problem	Language	Result	Execution time	Memory
703773		weakweakweak	Volontiranje (COCI21_volontiranje)	C++14	10 / 110	47 ms	71592 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};
vector<pii> lv[N];
vector<vector<int>>ans;
set<int>st[N];

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]=lv[fr[i]-1][l].sc;
    }

    for(auto i:st[lis.size()]){
        vector<int>v;
        bool br=0;
        for(int t=lis.size(); t>1; t--){
            v.push_back(i);
            auto it=st[t-1].lower_bound(lb[i]), it2=st[t-1].lower_bound(i);
            if(it==it2){
                    br=1;
                    break;}
            i=*it;
        }
        v.push_back(i);
        if(v.size()!=lis.size()||br)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;}

Compilation message (stderr)

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

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