Cod sursa(job #3286735)

Utilizator unomMirel Costel unom Data 14 martie 2025 16:36:17
Problema Range minimum query Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>

using namespace std;

int v[100001];
int n, m;
int sg[300000];

void construct(int input[], int segmentTree[], int low, int high, int pos)
{
    if(low == high)
    {
        segmentTree[pos] = input[low];
        return;
    }
    int mid = (low+high) / 2;

    construct(input, segmentTree, low, mid, pos * 2 + 1);
    construct(input, segmentTree, mid+1, high, pos * 2 + 2);
    segmentTree[pos] = min(segmentTree[2 * pos + 1], segmentTree[2 * pos + 1]);
}

int main()
{
    ifstream f("rmq.in");
    ofstream g("rmq.out");
    f>>n>>m;
    for(int i = 0; i<n; i++)
    {
        f>>v[i];
    }

    for(int i = 0; i<300000; i++)
    {
        sg[i] = 2e9;
    }

    construct(v, sg, 0, 3, 0);

    for(int i = 0; i<17; i++)
    {
        g<<sg[i]<<" ";
    }

    return 0;
}