답안 #72350

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72350	2018-08-26T07:22:24 Z	동진의 (#2167, kdk3776, define_chan, Jinpari)	흔한 자료구조 문제 (FXCUP3_easy)	C++17	0 / 100	2 ms	472 KB

easy

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
using namespace std;
int N, Q, L, R;
int input[100005];
int segTree[400020];
int max_num = 0x7FFFFFFF;
int min_num = 0;
int i, j, lo, hi;
int fake_n;
int ql, qh;
int nl, nh;

void construct_tree_min(int input[], int segTree[], int low, int high, int pos) {
	if (low == high)
	{
		segTree[pos] = input[low];
		return;
	}
	int mid = (low + high) / 2;
	construct_tree_min(input, segTree, low, mid, 2 * pos + 1);
	construct_tree_min(input, segTree, mid + 1, high, 2 * pos + 2);
	segTree[pos] = min(segTree[2 * pos + 1], segTree[2 * pos + 2]);
}

void rangeQuery(int segTree[], int value, int low, int high, int pos) {
	
	//printf("low %d high %d value %d\n", low, high, segTree[pos] );
	if (segTree[pos] == value) // overlap
	{
		//printf("call %d %d\n",low,high);
		ql = low;
		qh = high;
		return;
	}
	if (high == low)  // no overlap
	{
		return;
	}
	int mid = (low + high) / 2;
	rangeQuery(segTree, value, low, mid, 2 * pos + 1);
	rangeQuery(segTree, value, mid + 1, high, 2 * pos + 2);
}
/*
int rangeQuery(int segTree[], int qlow, int qhigh, int low, int high, int pos) {
	if (qlow <= low && high <= qhigh) // overlap
		return segTree[pos];
	if (qlow > high || qhigh < low)  // no overlap
		return max_num;
	int mid = (low + high) / 2;
	return min(rangeQuery(segTree, qlow, qhigh, low, mid, 2 * pos + 1), rangeQuery(segTree, qlow, qhigh, mid + 1, high, 2 * pos + 2));
}
*/

void fake_nf()
{
	fake_n = 1;
	while (N > fake_n)
	{
		fake_n *= 2;
	}
}

int main()
{
	//ip1 N Q
	scanf(" %d %d", &N, &Q);

	fake_nf();
	//ip2
	for (int i = 1; i <= N; i++)
	{
		scanf(" %d", &input[i]);
	}
	//ip_fake
	for (int i = N + 1; i <= fake_n; i++)
		input[i] = max_num;

	//Makig tree
	construct_tree_min(input, segTree, 1, fake_n, 0);

	//print tree
	//for (int i = 0; i < fake_n * 4; i++)
	//{
	//	printf("%d ", segTree[i]);
	//}
	//printf("\n");

	//Query
	for (int i = 0; i < Q; i++)
	{
		int time;
		scanf(" %d", &time);
		
		for (int i = 0; i < time; i++)
		{
			int a;
			scanf(" %d", &a);
			rangeQuery( segTree,  a, 1, (1+ fake_n)/2, 1 );
			rangeQuery(segTree, a, (1 + fake_n)/ 2+1, fake_n, 2);

			if (i == 0)
			{
				//printf("1\n");
				nl = ql;
				nh = qh;
			}
			else
			{
				if (qh + 1 == nl)
				{
					//printf("2\n");
					nl = ql;
				}
				else if (nh + 1 == ql)
				{
					//printf("3 nh %d  ql %d\n",nh,ql);
					nh = qh;
				}
				else
				{
					printf("-1\n");
					break;
				}
			}

			if (i == time - 1)
			{
				if (nh > N)
					nh = N;
				printf("%d %d\n", nl, nh);
			}
		}
	}

	return 0;
}

Compilation message

easy.cpp: In function 'int main()':
easy.cpp:69: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:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %d", &input[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~
easy.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %d", &time);
   ~~~~~^~~~~~~~~~~~~~
easy.cpp:100:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %d", &a);
    ~~~~~^~~~~~~~~~~

Subtask #1

0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Correct
2	Incorrect	2 ms	472 KB	Wrong
3	Halted	0 ms	0 KB	-

Subtask #2

0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Correct
2	Incorrect	2 ms	472 KB	Wrong
3	Halted	0 ms	0 KB	-