This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
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]);
}
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));
}
int main()
{
//ip1 N Q
scanf(" %d %d", &N, &Q);
//ip2
for (int i = 1; i <= N; i++)
{
scanf(" %d", &input[i]);
}
//Makig tree
construct_tree_min(input, segTree, 1, N, 0);
//Query
for (int i = 0; i < Q; i++)
{
int a, b;
scanf(" %d %d", &a, &b);
printf("%d\n",rangeQuery(segTree, a, b, 1, N, 0) );
}
return 0;
}
Compilation message (stderr)
easy.cpp: In function 'int main()':
easy.cpp:39: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:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d", &input[i]);
~~~~~^~~~~~~~~~~~~~~~~~
easy.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |