Submission #67849

#	Time	Username	Problem	Language	Result	Execution time	Memory
67849		imsifile	Easy Data Structure Problem (FXCUP3_easy)	C++98	0 / 100	2 ms	376 KiB

easy

#include<stdio.h>
#include<algorithm>
using namespace std;

int N, Q, j2, ba[101010], wi[101010], itr[401010];

int min2(int a, int b){
	if(a==0) return b;
	if(b==0) return a;
	return a>b?b:a;
}

int lca(int a, int b){
	while(a!=b){
		if(a<b) b>>=1;
		else a>>=1;
	}
	return a;
}

int rll(int ix){
	if(ix>=j2) return ix;
	for(ix=ix*2+1; ix<j2; ix<<=1);
	return ix;
}

bool comp(const int &x, const int &y) { return wi[x] < wi[y]; }
int C, su[40], se[40][2], nod[40], lv[40];

void query(){
	scanf("%d", &C);
	for(int i=0; i<C; i++) scanf("%d", &su[i]), lv[i]=0;
	if(C == 1){
		printf("%d %d\n", wi[su[0]]-j2+1, wi[su[0]]-j2+1);
		return;
	}
	sort(su, su+C, comp);
	for(int i=0; i<C-1; i++){
		se[i+1][0] = rll(lca(wi[su[i]], wi[su[i+1]]));
		se[i][1] = se[i+1][0]-1;
	}
	for(int i=1; i<C-1; i++){
		int s=se[i][0], e=se[i][1];
		while(s!=e){
			if(s%2 || e%2==0){ puts("-1"); return; }
			s>>=1, e>>=1, lv[i]++;
		}
		if(itr[s] != su[i]){ puts("-1"); return; }
		nod[i]=s;
	}
	int ix;
	for(ix=se[0][1]; itr[ix]!=su[0];){
		if(ix%2==0){ puts("-1"); return; }
		ix>>=1, lv[0]++;
	}
	nod[0]=ix;
	for(ix=se[C-1][0]; itr[ix]!=su[C-1];){
		if(ix%2==1){ puts("-1"); return; }
		ix>>=1, lv[C-1]++;
	}
	nod[C-1]=ix;

	if(C==2){
		if(nod[0]/2 == nod[1]/2){ puts("-1"); return; }
	}
	else{
		int l, r;
		for(l=0; l<C-1; l++){
			if(lv[l] >= lv[l+1]) break;
		}
		for(r=C-1; r>0; r--){
			if(lv[r] >= lv[r-1]) break;
		}
		if(r-l > 1){ puts("-1"); return; }
		if(r-l == 1 && nod[l]/2 == nod[r]/2){ puts("-1"); return; }
	}

	int a, b;
	for(a=nod[0]; a<j2; a<<=1);
	for(b=nod[C-1]; b<j2; b=b*2+1);
	printf("%d %d\n", a-j2+1, b-j2+1);
}

int main(){
	scanf("%d%d", &N, &Q);
	for(j2=1; j2<N; j2<<=1);
	for(int i=0; i<N; i++) scanf("%d", &ba[i]), wi[ba[i]]=j2+i, itr[j2+i]=ba[i];
	for(int i=j2; --i;) itr[i]=min2(itr[i*2], itr[i*2+1]);
	while(Q--) query();
	return 0;
}

Compilation message (stderr)

easy.cpp: In function 'void query()':
easy.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &C);
  ~~~~~^~~~~~~~~~
easy.cpp:32:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<C; i++) scanf("%d", &su[i]), lv[i]=0;
                         ~~~~~~~~~~~~~~~~~~~^~~~~~~~~
easy.cpp: In function 'int main()':
easy.cpp:85: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:60: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++) scanf("%d", &ba[i]), wi[ba[i]]=j2+i, itr[j2+i]=ba[i];
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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