oj.uz

Submission #67850

# Submission time Handle Problem Language Result Execution time Memory
67850 2018-08-15T11:07:04 Z 검수컵(#1978, imsifile) Easy Data Structure Problem (FXCUP3_easy) C++
100 / 100
 67 ms 2380 KB 
#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);
	if(b-j2 >= N){ puts("-1"); return; }
	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

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:86: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:88: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
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Correct
2 Correct 2 ms 396 KB Correct
3 Correct 2 ms 548 KB Correct
4 Correct 9 ms 548 KB Correct
5 Correct 3 ms 548 KB Correct
6 Correct 16 ms 688 KB Correct
7 Correct 10 ms 688 KB Correct
8 Correct 15 ms 688 KB Correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Correct
2 Correct 2 ms 396 KB Correct
3 Correct 2 ms 548 KB Correct
4 Correct 9 ms 548 KB Correct
5 Correct 3 ms 548 KB Correct
6 Correct 16 ms 688 KB Correct
7 Correct 10 ms 688 KB Correct
8 Correct 15 ms 688 KB Correct
9 Correct 21 ms 2308 KB Correct
10 Correct 23 ms 2308 KB Correct
11 Correct 33 ms 2308 KB Correct
12 Correct 64 ms 2308 KB Correct
13 Correct 47 ms 2308 KB Correct
14 Correct 60 ms 2344 KB Correct
15 Correct 60 ms 2344 KB Correct
16 Correct 67 ms 2380 KB Correct
17 Correct 62 ms 2380 KB Correct