제출 #1163473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163473		salmon	Volontiranje (COCI21_volontiranje)	C++20	0 / 110	0 ms	320 KiB

Main

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

int N;
int parent[1100100];
int ind[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{
			root -> remove(-ii.second);
			parent[h] = -ii.second;
			root -> update(h,ii.first + 1);
		}
	}
	
	int big = (root -> query(0,N-1)).first;
	
	vector<vector<int>> v;
	
	while(true){
		pair<int,int> ii = root -> query(0,N-1);
		if(ii.first != big) break;
		root -> remove(-ii.second);
		
		vector<int> temp = {ind[-ii.second]};
		int c = -ii.second;
		while(parent[c] != -1){
			c = parent[c];
			temp.push_back(ind[c]);
		}
		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 ",i + 1);
		}
		printf("\n");
	}
	
	
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:105: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=]
  105 |         printf("%d %d\n",v.size(), big);
      |                 ~^       ~~~~~~~~
      |                  |             |
      |                  int           std::vector<std::vector<int> >::size_type {aka long unsigned int}
      |                 %ld
Main.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
Main.cpp:71:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |                 scanf(" %d",&h);
      |                 ~~~~~^~~~~~~~~~

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