oj.uz

Submission #67848

# Submission time Handle Problem Language Result Execution time Memory
67848 2018-08-15T11:05:18 Z 검수컵(#1978, imsifile) Easy Data Structure Problem (FXCUP3_easy) C++
33 / 100
 51 ms 3404 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -