답안 #67848

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67848	2018-08-15T11:05:18 Z	검수컵(#1978, imsifile)	흔한 자료구조 문제 (FXCUP3_easy)	C++	33 / 100	51 ms	3404 KB

easy

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

int N, Q, j2, itr[401010];

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

struct mymy {
	int l, r; vector<int> vv;
	void rmq(int s, int e){
		l=s+1, r=e+1; s+=j2, e+=j2;
		vv.clear();
		while(1){
			if(s%2) vv.push_back(itr[s]), s++;
			if(e%2==0) vv.push_back(itr[e]), e--;
			if(s>e) break;
			s>>=1, e>>=1;
		}
		sort(vv.begin(), vv.end());
	}
} mys[6060];

vector<int> con[40];
int mcn;

void query(){
	int C; vector<int> vs;
	scanf("%d", &C);
	vs.clear();
	for(int i=0; i<C; i++){
		int a; scanf("%d", &a);
		vs.push_back(a);
	}
	for(int i=0; i<con[C].size(); i++){
		int x = con[C][i], fl=1;
		for(int j=0; j<C; j++){
			if(vs[j] != mys[x].vv[j]){ fl=0; break; }
		}
		if(fl){ printf("%d %d\n", mys[x].l, mys[x].r); return; }
	}
	puts("-1");
}

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

	for(int i=0; i<N; i++){
		for(int j=i; j<N; j++){
			mys[mcn].rmq(i,j);
			con[mys[mcn].vv.size()].push_back(mcn);
			mcn++;
		}
	}

	for(int t=0; t<Q; t++) query();
	return 0;
}

Compilation message

easy.cpp: In function 'void query()':
easy.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<con[C].size(); i++){
               ~^~~~~~~~~~~~~~
easy.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &C);
  ~~~~~^~~~~~~~~~
easy.cpp:37:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; scanf("%d", &a);
          ~~~~~^~~~~~~~~~
easy.cpp: In function 'int main()':
easy.cpp:51: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:53:30: 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", &itr[j2+i]);
                         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1

33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	632 KB	Correct
2	Correct	2 ms	632 KB	Correct
3	Correct	2 ms	800 KB	Correct
4	Correct	18 ms	800 KB	Correct
5	Correct	9 ms	856 KB	Correct
6	Correct	47 ms	1004 KB	Correct
7	Correct	36 ms	1036 KB	Correct
8	Correct	51 ms	1100 KB	Correct

Subtask #2

0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	632 KB	Correct
2	Correct	2 ms	632 KB	Correct
3	Correct	2 ms	800 KB	Correct
4	Correct	18 ms	800 KB	Correct
5	Correct	9 ms	856 KB	Correct
6	Correct	47 ms	1004 KB	Correct
7	Correct	36 ms	1036 KB	Correct
8	Correct	51 ms	1100 KB	Correct
9	Runtime error	22 ms	3404 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Halted	0 ms	0 KB	-