Submission #853775

#	Time	Username	Problem	Language	Result	Execution time	Memory
853775		NotLinux	Volontiranje (COCI21_volontiranje)	C++17	10 / 110	1 ms	604 KiB

Main

#include <bits/stdc++.h>
using namespace std;
struct SEGT{
	vector < int > tree;
	int sz;
	SEGT(int x){
		x += 5;
		sz = x;
		tree.assign(4 * sz , 0);
	}
	void _update(int ind , int l , int r , int qp , int qv){
		if(l == r){
			tree[ind] = qv;
			return;
		}
		int mid = (l+r)/2;
		if(mid >= qp){
			_update(ind*2,l,mid,qp,qv);
		}
		else{
			_update(ind*2+1,mid+1,r,qp,qv);
		}
		tree[ind] = max(tree[ind*2] , tree[ind*2+1]);
	}
	void update(int p , int v){
		_update(1,1,sz,p,v);
	}
	int _query(int ind , int l , int r , int ql , int qr){
		if(l >= ql and r <= qr){
			return tree[ind];
		}
		else if(l > qr or r < ql){
			return 0;
		}
		else{
			int mid = (l+r)/2;
			return max(_query(ind*2,l,mid,ql,qr) , _query(ind*2+1,mid+1,r,ql,qr));
		}
	}
	int query(int l , int r){
		return _query(1,1,sz,l,r);
	}
};
void solve(){
	int n;
	cin >> n;
	int arr[n],lis[n],nxt[n],mx = 0;
	memset(nxt , -1 , sizeof(nxt));
	SEGT segt(n);
	multiset < pair < int , int > > q[n+1];
	for(int i = 0;i<n;i++){
		cin >> arr[i];
		lis[i] = segt.query(1,arr[i]) + 1;
		mx = max(mx , lis[i]);
		q[lis[i]].insert({i,arr[i]});
		segt.update(arr[i],lis[i]);
	}
	for(int i = n;i>0;i--){
		if(q[i].empty()){
			continue;
		}
		vector < pair < int , int > > willadd;
		while(q[i].size()){
			pair < int , int > cur = *(--q[i].end());
			q[i].erase(--q[i].end());
			while(q[i-1].size()){
				pair < int , int > cand = *(--q[i-1].end());
				q[i-1].erase(--q[i-1].end());
				if(cand.first < cur.first and cand.second < cur.second){
					willadd.push_back(cand);
					nxt[cand.first] = cur.first;
					break;
				}
				else if(cand.second > cur.second){
					willadd.push_back(cand);
					break;
				}
			}
		}
		for(auto itr : willadd){
			q[i-1].insert(itr);
		}
	}
	int valid[n];
	memset(valid , 0 , sizeof(valid));
	vector < vector < int > > ans;
	for(int i = n-1;i>=0;i--){
		if(nxt[i] == -1){
			valid[i] = 1;
		}
		else{
			valid[i] = valid[nxt[i]] + 1;
		}
		if(valid[i] == mx){
			vector < int > locans;
			int cur = i;
			do {
				locans.push_back(cur);
				cur = nxt[cur];
			} while(cur != -1);
			ans.push_back(locans);
		}
	}
	cout << ans.size() << " " << mx << '\n';
	for(auto itr : ans){
		for(auto itr1 : itr){
			cout << itr1+1 << " ";
		}
		cout << '\n';
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

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