oj.uz

Submission #67721

# Submission time Handle Problem Language Result Execution time Memory
67721 2018-08-15T09:09:17 Z imsifile Easy Data Structure Problem (FXCUP3_easy) C++
100 / 100
 61 ms 2476 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 248 KB Correct
2 Correct 2 ms 392 KB Correct
3 Correct 2 ms 432 KB Correct
4 Correct 9 ms 468 KB Correct
5 Correct 3 ms 468 KB Correct
6 Correct 20 ms 528 KB Correct
7 Correct 12 ms 528 KB Correct
8 Correct 13 ms 588 KB Correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Correct
2 Correct 2 ms 392 KB Correct
3 Correct 2 ms 432 KB Correct
4 Correct 9 ms 468 KB Correct
5 Correct 3 ms 468 KB Correct
6 Correct 20 ms 528 KB Correct
7 Correct 12 ms 528 KB Correct
8 Correct 13 ms 588 KB Correct
9 Correct 20 ms 2260 KB Correct
10 Correct 24 ms 2260 KB Correct
11 Correct 23 ms 2260 KB Correct
12 Correct 49 ms 2260 KB Correct
13 Correct 48 ms 2260 KB Correct
14 Correct 61 ms 2476 KB Correct
15 Correct 57 ms 2476 KB Correct
16 Correct 59 ms 2476 KB Correct
17 Correct 55 ms 2476 KB Correct