Submission #72235

#	Time	Username	Problem	Language	Result	Execution time	Memory
72235		BOJ 8481 (#118)	Easy Data Structure Problem (FXCUP3_easy)	C++17	33 / 100	686 ms	1280 KiB

easy

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int n,q;
int arr[110];
int pos[110];
int x[400];
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]]);
	}
	for(int s=minx; s>=1; s--){
		for(int e=maxx; e<=n; 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);
	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:14: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:48: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:64: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:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &arr[i]);
   ~~~~~^~~~~~~~~~~~~~~
easy.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c);
   ~~~~~^~~~~~~~~~
easy.cpp:88:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &temp);
    ~~~~~^~~~~~~~~~~~~

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