#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);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Correct |
| 2 |
Incorrect |
2 ms |
472 KB |
Wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Correct |
| 2 |
Incorrect |
2 ms |
472 KB |
Wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
