Submission #72262

#	Time	Username	Problem	Language	Result	Execution time	Memory
72262		BOJ 8481 (#118)	Easy Data Structure Problem (FXCUP3_easy)	C++17	0 / 100	4 ms	2036 KiB

easy

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <memory.h>
// #include <map>
using namespace std;
int n,q;
int arr[100010];
int pos[100010];
int x[400000];
int base;
// map<pair<int, int>, vector<int> > db;
bool same(vector<int> a, vector<int> b){
	if(a.size() != b.size()) return false;
	for(int i=0; i<a.size(); i++){
		if(a[i] != b[i]) return false;
	}
	return true;
}
vector<int> get_list(int s, int e){
	vector<int> ret;
	s += (base-1);
	e += (base-1);
	if(s == e){
		ret.push_back(x[s]);
	}
	while(s < e){
		if(s % 2 == 1){
			ret.push_back(x[s]);
			s += 1;
		}
		if(e % 2 == 0){
			ret.push_back(x[e]);
			e -= 1;
		}
		s /= 2;
		e /= 2;
		if(s == e){
			ret.push_back(x[s]);
		}
	}
	sort(ret.begin(), ret.end());
	return ret;
}
void answer_query(vector<int> query){
	int minx;
	int maxx = -1;
	minx = n+10;
	for(int i=0; i<query.size(); i++){
		minx = min(minx, pos[query[i]]);
		maxx = max(maxx, pos[query[i]]);
	}
	int min_s = minx + (base-1);
	while(x[min_s] == x[min_s/2]){
		min_s /= 2;
	}
	while(min_s < base){
		min_s *= 2;
	}
	int max_e = maxx + (base-1);
	while(x[max_e] == x[max_e/2]){
		max_e /= 2;
	}
	while(max_e < base){
		max_e *= 2;
		max_e += 1;
	}
	min_s -= (base-1);
	max_e -= (base-1);
	// puts("eh");
	// printf("%d %d %d %d\n", min_s, minx, maxx, max_e);
	for(int s=minx; s>=min_s; s--){
		for(int e=maxx; e<=max_e; e++){
			// if(same(db[make_pair(s,e)], query)){
			if(same(get_list(s, e), query)){
				printf("%d %d\n", s, e);
				return;
			}
		}
	}
	printf("-1\n");
}
int main(){
	scanf("%d%d", &n, &q);
	memset(x, n+10, sizeof(x));
	for(int i=1; i<=n; i++){
		scanf("%d", &arr[i]);
		pos[arr[i]] = i;
	}
	base = 1;
	while(base < n) base *= 2;
	for(int i=1; i<=n; i++){
		x[base+i-1] = arr[i];
	}
	for(int i=base-1; i>=1; i--){
		x[i] = min(x[2*i], x[2*i+1]);
	}
	// for(int s=1; s<=n; s++){
	// 	for(int e=s; e<=n; e++){
	// 		db[make_pair(s,e)] = get_list(s, e);
	// 	}
	// }
	while(q--){
		vector<int> query;
		int c;
		scanf("%d", &c);
		for(int i=1; i<=c; i++){
			int temp;
			scanf("%d", &temp);
			query.push_back(temp);
		}
		answer_query(query);
	}
}

Compilation message (stderr)

easy.cpp: In function 'bool same(std::vector<int>, std::vector<int>)':
easy.cpp:15:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<a.size(); i++){
               ~^~~~~~~~~
easy.cpp: In function 'void answer_query(std::vector<int>)':
easy.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<query.size(); i++){
               ~^~~~~~~~~~~~~
easy.cpp: In function 'int main()':
easy.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~
easy.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &arr[i]);
   ~~~~~^~~~~~~~~~~~~~~
easy.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c);
   ~~~~~^~~~~~~~~~
easy.cpp:109:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &temp);
    ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 33
• Subtask 2: 0 / 67