Submission #1163506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163506		zhehan	Volontiranje (COCI21_volontiranje)	C++20	0 / 110	0 ms	324 KiB

Main

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

typedef pair<int,int> ii;

vector<ii> ft;

void upd(int p, ii v){
	while(p<(int)ft.size()){
		if(ft[p].first == v.first){
			ft[p] = min(ft[p],v);
		}else{
			ft[p] = max(ft[p],v);
		}
		p+=p&(-p);
	}
}
ii qry(int p){
	ii ans=ii(0,-1);
	while(p>0){
		ans = max(ft[p],ans);
		p-=p&(-p);
	}
	return ans;
}

signed main(){
	int n, maxl;
	cin>>n;
	vector<int> v(n,0);
	for(int i=0;i<n;++i){
		cin>>v[i];
	}
	map<int,vector<ii>> lis;
	ft = vector<ii> (n+1,ii(0,-1));
	for(int i=0;i<n;++i){
		auto curr = qry(v[i]);
		curr.first++;
		upd(v[i],ii(curr.first,i));
		lis[curr.first].push_back(ii(i,curr.second));
		maxl = max(maxl,curr.first);
	}
	vector<int> visited(n,0);
	vector<vector<int>> ans;
	int cnt=0;
	for(auto e:lis[maxl]){
		vector<int> ind{e.first};
		ii curr = e;
		int pos=maxl-1;
		auto nextind = lis[pos].begin();
		bool pass=true;
		visited[curr.first]=1;
		while(pass){
            if(pos==0) break;
			nextind = lower_bound(lis[pos].begin(),lis[pos].end(),ii(curr.second,-1));
			pos--;
			while(visited[(*nextind).first]==1){
				nextind++;
				if(nextind==lis[pos].end()){
					pass=false;
					break;
				}
			}
			visited[(*nextind).first]=1;
			ind.push_back((*nextind).first);
			if((*nextind).second==-1){
				break;
			}

			curr=*nextind;
		}
		if(pass){
			cnt++;
			ans.push_back(ind);
		}
	}
	cout<<cnt<<' '<<maxl<<'\n';
	for(auto e:ans){
        for(int i=e.size()-1;i>=0;--i){
            cout<<e[i]+1<<' ';
        }
        cout<<'\n';
	}
}

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