Pagini recente » Borderou de evaluare (job #2899059) | Borderou de evaluare (job #72305) | Cod sursa (job #1356823)
#include <stdio.h>
#include <limits.h>
#define N_MAX 100489 // Cel mai mic patrat perfect mai mare ca 100.000
#define R_MAX 317
#define DEBUG 0
int v[N_MAX];
int up[R_MAX][R_MAX], dn[R_MAX][R_MAX], sub[R_MAX][R_MAX];
int main()
{
FILE *fin, *fout;
fin = fopen("rmq.in", "r");
fout = fopen("rmq.out", "w");
// Citire
int N, M;
fscanf(fin, "%d%d", &N, &M);
int i, j;
for (i = 0; i < N; ++i) {
fscanf(fin, "%d", v + i);
}
// Bbl
int x = N - 1, y = 1;
while (x > y) {
x = (x + y) / 2;
y = (N - 1) / x;
}
int Np = (x + 1) * (x + 1);
int r = x + 1;
if (DEBUG) {
printf("%d\n", Np);
}
for (i = N; i < Np; ++i) {
v[i] = INT_MAX;
}
N = Np;
if (DEBUG) {
/*for (i = 0; i < N; ++i) {
printf("%d ", v[i]);
}*/
}
// Precalculare
for (i = 0; i < r; ++i) {
int ir = i * r;
up[i][0] = v[ir];
dn[i][r - 1] = v[ir + r - 1];
for (j = 1; j < r; ++j) {
int test = v[ir + j];
up[i][j] = (up[i][j - 1] < test ? up[i][j - 1] : test);
}
for (j = r - 2; j >= 0; --j) {
int test = v[ir + j];
dn[i][j] = (dn[i][j + 1] < test ? dn[i][j + 1] : test);
}
}
for (i = 0; i < r; ++i) {
sub[i][i] = up[i][r - 1];
for (j = i + 1; j < r; ++j) {
sub[i][j] = (sub[i][j - 1] < up[j][r - 1] ? sub[i][j - 1] : up[j][r - 1]);
}
}
for (i = 0; i < M; ++i) {
int e, f;
fscanf(fin, "%d%d", &e, &f);
--e; --f;
int er = e / r, fr = f / r;
if (er == fr) {
int min = INT_MAX;
for (int k = e; k <= f; ++k) {
min = (min < v[k] ? min : v[k]);
}
fprintf(fout, "%d\n", min);
} else {
int m1 = dn[er][e % r], m2 = sub[er + 1][fr - 1], m3 = up[fr][f % r];
int min = INT_MAX;
if (m1 < min) {
min = m1;
}
if (m2 < min && fr - er >= 2) {
min = m2;
}
if (m3 < min) {
min = m3;
}
if (DEBUG) {
printf("%d %d %d\n", m1, m2, m3);
}
fprintf(fout, "%d\n", min);
}
}
fclose(fin);
fclose(fout);
return 0;
}