oj.uz

Submission #851395

# Submission time Handle Problem Language Result Execution time Memory
851395 2023-09-19T17:26:49 Z NotLinux Volontiranje (COCI21_volontiranje) C++17
10 / 110
 1 ms 456 KB 
#include <bits/stdc++.h>
using namespace std;
struct SEGT{//range max , point update
	vector < int > tree;
	int sz;
	SEGT(int x){
		x++;
		sz = x;
		tree.assign(4*x,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;
	SEGT segt(n+1);
	int p[n],lis[n],mx = 1;
	for(int i = 0;i<n;i++){
		cin >> p[i];
		lis[i] = 1 + segt.query(1,p[i]);
		segt.update(p[i] , lis[i]);
		mx = max(mx , lis[i]);
	}
	set < pair < int , int > > v[mx+2];
	vector < int > starting_points;
	int go[n];
	memset(go , -1 , sizeof(go));
	for(int i = n-1;i>=0;i--){
		if(v[lis[i]+1].size()){
			auto it = v[lis[i]+1].lower_bound(make_pair(p[i],1e9 + 7));
			if(it == v[lis[i]+1].end()){
				continue;
			}
			go[i] = (*it).second;
			v[lis[i]+1].erase(it);
			v[lis[i]].insert({p[i],i});
			if(lis[i] == 1){
				starting_points.push_back(i);
			}
		}
		else if(lis[i] == mx){
			v[lis[i]].insert({p[i],i});
			if(lis[i] == 1){
				starting_points.push_back(i);
			}
		}
	}
	cout << starting_points.size() << " " << mx << endl;
	for(auto itr : starting_points){
		int cur = itr;
		do{
			cout << cur+1 << " ";
			cur = go[cur];
		}while(cur != -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.0 / 10.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 456 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 456 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 456 KB Output is correct
26 Correct 0 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 360 KB Output is correct
31 Correct 1 ms 352 KB Output is correct
32 Correct 1 ms 352 KB Output is correct
33 Incorrect 1 ms 352 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 456 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 456 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 456 KB Output is correct
26 Correct 0 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 360 KB Output is correct
31 Correct 1 ms 352 KB Output is correct
32 Correct 1 ms 352 KB Output is correct
33 Incorrect 1 ms 352 KB Output isn't correct
34 Halted 0 ms 0 KB -