Cod sursa(job #3373661)

Utilizator MateiDiaconuDiaconu Matei Stefan MateiDiaconu Data 7 noiembrie 2026 15:17:38
Problema Arbori de intervale Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.18 kb
#include <iostream>

using namespace std;

#define MAXN 100000
const int SQ_N = 317;   // sqrt(MAXN)

int v[MAXN];
int batog[SQ_N + 1];

int query(int a, int b){
    int firstInterval, lastInterval, left, right, maxx;

    firstInterval = a / SQ_N * SQ_N;
    lastInterval = b / SQ_N * SQ_N;
    maxx = -1;

    if(firstInterval == lastInterval){
        while(a <= b){
            if(v[a] > maxx){
                maxx = v[a];
            }
            a++;
        }
        return maxx;
    }

    left = a;
    if(left % SQ_N > 0){
        while(left < firstInterval + SQ_N){
            if(v[left] > maxx){
                maxx = v[left];
            }
            left++;
        }
    }
    firstInterval = left / SQ_N;

    right = b;
    if(right % SQ_N > 0){
        while(right >= lastInterval){
            if(v[right] > maxx){
                maxx = v[right];
            }
            right--;
        }
    }
    lastInterval = right / SQ_N;

    while(firstInterval <= lastInterval){
        if(batog[firstInterval] > maxx){
            maxx = batog[firstInterval];
        }
        firstInterval++;
    }

    return maxx;
}

void update(int poz, int val){
    int interval, i;

    interval = poz / SQ_N * SQ_N;

    if(val > batog[interval]){
        batog[interval] = val;
    }
    else if(v[poz] == batog[interval]){
        v[poz] = val;
        for(i = interval * SQ_N; i < (interval + 1) * SQ_N; i++){
            if(v[i] > batog[interval]){
                batog[interval] = v[i];
            }
        }
    }

    v[poz] = val;
}

int main()
{
    FILE *fin, *fout;
    fin = fopen("arbint.in", "r");
    fout = fopen("arbint.out", "w");

    int n, m, i, op, a, b;

    fscanf(fin, "%d%d", &n, &m);

    for(i = 0; i < n; i++){
        fscanf(fin, "%d", &v[i]);

        batog[i / SQ_N] = max(batog[i / SQ_N], v[i]);
    }

    for(i = 0; i < m; i++){
        fscanf(fin, "%d%d%d", &op, &a, &b);

        if(op == 0){
            fprintf(fout, "%d\n", query(a - 1, b - 1));
        }
        else{
            update(a - 1, b);
        }
    }

    fclose(fin);
    fclose(fout);
    return 0;
}