제출 #72435

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72435		동진의 (#118)	흔한 자료구조 문제 (FXCUP3_easy)	C++17	0 / 100	2 ms	356 KiB

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 i, j, lo, hi;
int fake_n;
int ql, qh;
int nl, nh;
int Level;
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 level,  int pos ) {
	
	//printf("low %d high %d value %d\n", low, high, segTree[pos] );
	if (segTree[pos] == value && level == Level) // 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, level +1, 2 * pos + 1 );
	rangeQuery(segTree, value, mid + 1, high,level +1 , 2 * pos + 2);
}

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

void print_segTree()
{
	for (int i = 0; i < fake_n * 2 -1; i++)
	{
		printf("%d ", segTree[i]);
	}
	printf("\n");
}

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
	//print_segTree();
	

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

			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;
}

컴파일 시 표준 에러 (stderr) 메시지

easy.cpp: In function 'int main()':
easy.cpp:67: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:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %d", &input[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~
easy.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %d", &time);
   ~~~~~^~~~~~~~~~~~~~
easy.cpp:96: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
• Subtask 2: 0 / 67