Submission #1163523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163523		salmon	Volontiranje (COCI21_volontiranje)	C++20	110 / 110	881 ms	198488 KiB

Main

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

int N;
int parent[1100100];
int ind[1100100];
vector<pair<int,int>> s[1100100];

struct node{

	int s, e, m;
	pair<int,int> v;
	node *l, *r;
	
	node(int S, int E){
		s = S;
		e = E;
		m = (s + e)/2;
		
		v = {0,s};
		
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1, e);
		}
	}
	
	pair<int,int> query(int S, int E){
		if(S <= s && e <= E) return v;
		
		pair<int,int> V = {0,-1};
		
		if(S <= m) V = max(V, l-> query(S,E));
		if(m < E) V = max(V, r-> query(S,E));
		return V;
	}
	
	void update(int i, int k){
		if(s == e){
			v = {k,i};
			return;
		}
		
		if(i <= m) l -> update(i,k);
		else r -> update(i,k);
		
		v = max(l -> v, r -> v);
	}
	
	void remove(int i){
		if(s == e){
			v = {0,i};
			return;
		}
		
		if(i <= m) l -> remove(i);
		else r -> remove(i);
		
		v = max(l -> v, r -> v);
	}
	
}*root;

int main(){
	
	scanf(" %d",&N);
	
	root = new node(0,N - 1);
	
	for(int i = 0; i < N; i++){
		int h;
		scanf(" %d",&h);
		h--;
		ind[h] = i;
		pair<int,int> ii = root -> query(0,h);
		if(ii.first == 0){
			root -> update(h,1);
			parent[h] = -1;
		}
		else{
			parent[h] = ii.second;
			root -> update(h,ii.first + 1);
		}
		s[ii.first + 1].push_back({h,i});
	}
	
	int big = (root -> query(0,N-1)).first;
	
	vector<vector<int>> v;
	
	while(true){
		if(s[big].empty()) break;
		pair<int,int> ii = {big,s[big].back().first};
		s[big].pop_back();
		
		vector<int> temp = {ii.second};
		
		int c = ii.second;
		int num = big - 1;
		
		while(true){
			if(num == -1) break;
			
			pair<int,int> ii1 = {-1,-1};
			while(s[num].size() != 0 && s[num].back().second > ind[temp.back()] ){
				s[num].pop_back();
			}
			if(s[num].size() == 0) break;
			if(s[num].back().first > temp.back()){
				if(num == big - 1) break;
				else{
					temp.pop_back();
					num++;
				}
			}
			else{
				temp.push_back(s[num].back().first);
				s[num].pop_back();
				num--;
			}
		}
		
		if(temp.size() != big) continue;
		else{
			reverse(temp.begin(), temp.end());
			v.push_back(temp);
		}
	}
	
	printf("%d %d\n",v.size(), big);
	
	for(vector<int> temp : v){
		for(int i : temp){
			printf("%d ",ind[i] + 1);
		}
		printf("\n");
	}
	
	
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:130:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
  130 |         printf("%d %d\n",v.size(), big);
      |                 ~^       ~~~~~~~~
      |                  |             |
      |                  int           std::vector<std::vector<int> >::size_type {aka long unsigned int}
      |                 %ld
Main.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
Main.cpp:72:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |                 scanf(" %d",&h);
      |                 ~~~~~^~~~~~~~~~

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