oj.uz

Submission #853831

# Submission time Handle Problem Language Result Execution time Memory
853831 2023-09-25T09:54:34 Z NotLinux Volontiranje (COCI21_volontiranje) C++17
50 / 110
 95 ms 36888 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
const int LIM = 1e6;
int sayac = 0;
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);
	}
};
int n,arr[N],lis[N],nxt[N],mx = 0;
priority_queue < pair < int , int > > q[N];
vector < vector < int > > ans;
vector < int > locans;
bool dfs(int node){
	if(sayac++ > LIM){
		cout << "0 1" << endl;
		exit(0);
	}
	//cout << node << " " << arr[node] << endl;
	if(lis[node] == 1){
		locans.push_back(node);
		if(mx == 1){
			ans.push_back(locans);
			locans.clear();
		}
		return 1;
	}
	bool work = 0;
	while(q[lis[node]-1].size()){
		if(sayac++ > LIM){
			cout << "0 1" << endl;
			exit(0);
		}
		pair < int , int > cand = q[lis[node]-1].top();
		if(cand.first < node and cand.second < arr[node]){
			bool bl = dfs(cand.first);
			if(bl){
				work = 1;
				locans.push_back(node);
				q[lis[node]-1].pop();
				break;
			}
			else{
				q[lis[node]-1].pop();
			}
		}
		else if(cand.first > node and cand.second < arr[node]){
			q[lis[node]-1].pop();
		}
		else if(cand.first < node and cand.second > arr[node]){
			break;
		}
	}
	if(work == 0){
		return 0;
	}
	else if(work == 1 and lis[node] == mx){
		ans.push_back(locans);
		locans.clear();
	}
	return 1;
}
void solve(){
	memset(nxt , -1 , sizeof(nxt));
	cin >> n;
	SEGT segt(n);
	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]].push({i,arr[i]});
		segt.update(arr[i],lis[i]);
	}
	while(q[mx].size()){
		if(sayac++ > LIM){
			cout << "0 1" << endl;
			exit(0);
		}
		dfs(q[mx].top().first);
		q[mx].pop();
	}
	cout << ans.size() << " " << mx << endl;
	for(auto itr : ans){
		for(auto itr1 : itr){
			cout << itr1+1 << " ";
		}
		cout << endl;
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8792 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 1 ms 8796 KB Output is correct
13 Correct 2 ms 8796 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 1 ms 8796 KB Output is correct
17 Correct 2 ms 8792 KB Output is correct
18 Correct 1 ms 8792 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 2 ms 8796 KB Output is correct
21 Correct 1 ms 8796 KB Output is correct
22 Correct 1 ms 8796 KB Output is correct
23 Correct 1 ms 8796 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8792 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 1 ms 8796 KB Output is correct
13 Correct 2 ms 8796 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 1 ms 8796 KB Output is correct
17 Correct 2 ms 8792 KB Output is correct
18 Correct 1 ms 8792 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 2 ms 8796 KB Output is correct
21 Correct 1 ms 8796 KB Output is correct
22 Correct 1 ms 8796 KB Output is correct
23 Correct 1 ms 8796 KB Output is correct
24 Correct 2 ms 8796 KB Output is correct
25 Correct 1 ms 8796 KB Output is correct
26 Correct 2 ms 8796 KB Output is correct
27 Correct 2 ms 8796 KB Output is correct
28 Correct 2 ms 8796 KB Output is correct
29 Correct 2 ms 8796 KB Output is correct
30 Correct 3 ms 8796 KB Output is correct
31 Correct 2 ms 8796 KB Output is correct
32 Correct 2 ms 8796 KB Output is correct
33 Correct 2 ms 8796 KB Output is correct
34 Correct 2 ms 8992 KB Output is correct
35 Correct 2 ms 8796 KB Output is correct
36 Correct 2 ms 8796 KB Output is correct
37 Correct 2 ms 8796 KB Output is correct
38 Correct 2 ms 8796 KB Output is correct
39 Correct 1 ms 8796 KB Output is correct
40 Correct 2 ms 8796 KB Output is correct
41 Correct 1 ms 8796 KB Output is correct
42 Correct 2 ms 8796 KB Output is correct
43 Correct 2 ms 8796 KB Output is correct
44 Correct 1 ms 8796 KB Output is correct
45 Correct 2 ms 8796 KB Output is correct
46 Correct 2 ms 8792 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8792 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 1 ms 8796 KB Output is correct
13 Correct 2 ms 8796 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 1 ms 8796 KB Output is correct
17 Correct 2 ms 8792 KB Output is correct
18 Correct 1 ms 8792 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 2 ms 8796 KB Output is correct
21 Correct 1 ms 8796 KB Output is correct
22 Correct 1 ms 8796 KB Output is correct
23 Correct 1 ms 8796 KB Output is correct
24 Correct 2 ms 8796 KB Output is correct
25 Correct 1 ms 8796 KB Output is correct
26 Correct 2 ms 8796 KB Output is correct
27 Correct 2 ms 8796 KB Output is correct
28 Correct 2 ms 8796 KB Output is correct
29 Correct 2 ms 8796 KB Output is correct
30 Correct 3 ms 8796 KB Output is correct
31 Correct 2 ms 8796 KB Output is correct
32 Correct 2 ms 8796 KB Output is correct
33 Correct 2 ms 8796 KB Output is correct
34 Correct 2 ms 8992 KB Output is correct
35 Correct 2 ms 8796 KB Output is correct
36 Correct 2 ms 8796 KB Output is correct
37 Correct 2 ms 8796 KB Output is correct
38 Correct 2 ms 8796 KB Output is correct
39 Correct 1 ms 8796 KB Output is correct
40 Correct 2 ms 8796 KB Output is correct
41 Correct 1 ms 8796 KB Output is correct
42 Correct 2 ms 8796 KB Output is correct
43 Correct 2 ms 8796 KB Output is correct
44 Correct 1 ms 8796 KB Output is correct
45 Correct 2 ms 8796 KB Output is correct
46 Correct 2 ms 8792 KB Output is correct
47 Runtime error 95 ms 36888 KB Execution killed with signal 11
48 Halted 0 ms 0 KB -