Submission #1222440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222440		Octa_pe_info	Wall (IOI14_wall)	C++20	0 / 100	107 ms	8008 KiB

wall

#include <iostream>
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

struct arbore {

    bool flag;
    int mini,maxi;
    int l_mi,l_mx;
};

vector<arbore>aint;

///tip : 1=scad 2 cresc

void update(int nod,int st,int dr,int l,int r,int tip,int v) {

    if(l <= st && dr <= r) {

        ///cazuri
        if(tip == 1) {

            aint[nod] = {true,min(aint[nod].mini,v),min(aint[nod].maxi,v),min(aint[nod].l_mx,v),min(aint[nod].l_mi,v)};
        }

        if(tip == 2) {

            aint[nod] = {true,max(aint[nod].mini,v),max(aint[nod].maxi,v),max(aint[nod].l_mx,v),max(aint[nod].l_mi,v)};
        }
        return;
    }

    ///push
    if(aint[nod].flag) {

        aint[2*nod] = {true,max(aint[nod].l_mi,aint[2*nod].mini),min(aint[nod].l_mx,aint[2*nod].maxi),max(aint[nod].l_mi,aint[2*nod].l_mi),min(aint[nod].l_mx,aint[2*nod].l_mx)};
        aint[2*nod + 1] = {true,max(aint[nod].l_mi,aint[2*nod + 1].mini),min(aint[nod].l_mx,aint[2*nod + 1].maxi),max(aint[nod].l_mi,aint[2*nod + 1].l_mi),min(aint[nod].l_mx,aint[2*nod + 1].l_mx)};

        aint[nod].flag = false;
        aint[nod].l_mi = 0;
        aint[nod].l_mx = 1e9;
    }

    int md = (st+dr)/2;

    if(l <= md)
        update(2*nod,st,md,l,r,tip,v);

    if(r > md)
        update(2*nod + 1,md+1,dr,l,r,tip,v);

    aint[nod] = {false,max(aint[2*nod].mini,aint[2*nod + 1].mini),min(aint[2*nod].maxi,aint[2*nod + 1].maxi),0,(int)(1e9)};
}

int qeu(int nod,int st,int dr,int poz) {


    if(aint[nod].flag) {

        aint[2*nod] = {true,max(aint[nod].l_mi,aint[2*nod].mini),min(aint[nod].l_mx,aint[2*nod].maxi),max(aint[nod].l_mi,aint[2*nod].l_mi),min(aint[nod].l_mx,aint[2*nod].l_mx)};
        aint[2*nod + 1] = {true,max(aint[nod].l_mi,aint[2*nod + 1].mini),min(aint[nod].l_mx,aint[2*nod + 1].maxi),max(aint[nod].l_mi,aint[2*nod + 1].l_mi),min(aint[nod].l_mx,aint[2*nod + 1].l_mx)};

        aint[nod].flag = false;
        aint[nod].l_mi = 0;
        aint[nod].l_mx = 1e9;
    }

    if(st==dr)
        return aint[nod].mini;

    int md = (st+dr)/2;

    if(poz <= md)
        return qeu(2*nod,st,md,poz);
    else
        return qeu(2*nod + 1,md+1,dr,poz);
}

void buildWall(int n, int k,
               int op[], int left[], int right[],
               int height[], int finalHeight[]) {

    const int INF = 1000000000;

    aint.assign(4*n, {false, 0, 0, 0, INF});

    for (int i = 0; i < k; i++) {

        int tip = (op[i] == 1 ? 2 : 1);
        update(1, 0, n-1, left[i], right[i], tip, height[i]);
    }

    for (int j = 0; j < n; j++) {
        finalHeight[j] = qeu(1, 0, n-1, j);
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39