Cod sursa(job #2942259)

Utilizator samyro14Samy Dragos samyro14 Data 19 noiembrie 2022 14:28:11
Problema Energii Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("aimi.in");
ofstream fout("aimi.out");
const int maxn = 1e5;
int n, m;
int a[maxn + 2];
struct segtree{
    int minim, lazy;
}aint[4 * maxn + 2];
void read(){
    fin >> n;
    for(int i = 1; i <= n; ++i) fin >> a[i];
    fin >> m;
}
void build(int node, int st, int dr){
    if(st == dr){
        aint[node].minim = a[st];
        return ;
    }
    int mid = (st + dr) / 2;
    build(2 * node, st, mid);
    build(2 * node + 1, mid + 1, dr);
    aint[node].minim = min(aint[2 * node].minim, aint[2 * node + 1].minim);
}

void update_lazy(int node, int st, int dr){
    if(aint[node].lazy != -1){
        aint[node].minim = aint[node].lazy;
        if(st != dr){
            aint[2 * node].lazy = aint[node].lazy;
            aint[2 * node + 1].lazy = aint[node].lazy;
        }
         aint[node].lazy = -1;

    }
}
void update(int node, int st, int dr, int l, int r, int newval){


   if(st>dr) return;  //!!!

    update_lazy(node, st, dr);

    if (l>dr || r<st) return;//!!!

    if(st >= l && dr <= r){
        aint[node].minim=newval;
        if(st != dr){
            aint[2 * node].lazy = newval;
            aint[2 * node + 1].lazy = newval;
               }
        return ;
    }
    int mid = (st + dr) / 2;
    //if(l <= mid)       //l
        update(2 * node, st, mid, l, r, newval);
    //if(r > mid)        //r
        update(2 * node + 1, mid +1, dr, l, r, newval);
    aint[node].minim = min(aint[2 * node].minim, aint[2 * node + 1].minim);
}
int query(int node, int st, int dr, int ql, int qr){
    if(st>dr) return INT_MAX;

    update_lazy(node, st, dr);

    if(ql>dr || qr<st) return INT_MAX;

    if(st >= ql && dr <= qr)
        return aint[node].minim;

    int mid = (st + dr) / 2;
    int q1, q2;

    //if(mid >= ql)   //ql
        q1 = query(2 * node, st, mid, ql, qr);
    //if(mid < qr)    //qr
        q2 = query(2 * node + 1, mid + 1, dr, ql, qr);
    return min(q1, q2);
}

int main(){
    read();
    build(1, 1, n);

    for(int i = 1; i <= n; ++i)
        aint[i].lazy = aint[i * 2].lazy = aint[i * 2 + 1].lazy = -1;



    for(int i = 1; i <= m; ++i){
        int op, x, y, val; fin >> op;
        if(op == 1) {
            fin >> x >> y;

           fout << query(1, 1, n, x, y) << "\n";

        }
        else{
            fin >> x >> y >> val;

            update(1, 1, n, x, y, val);

        }

    }
    return 0;
}