Submission #566014

#	Time	Username	Problem	Language	Result	Execution time	Memory
566014		Leo121	Wall (IOI14_wall)	C++14	0 / 100	270 ms	13936 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

struct node {
    bool lazy;
    int alto;
    int bajo;
    bool ultimo;
};

const int maxn = 2e6;
node st[4 * maxn + 1];
int valu[maxn];

void push(int nodo, int l, int r){
    if(!st[nodo].lazy){
        return;
    }
    if(l == r){
        if(st[nodo].alto == -1){
            valu[l] = min(valu[l], st[nodo].bajo);
        }
        else if(st[nodo].bajo == -1){
            valu[l] = max(valu[l], st[nodo].alto);
        }
        else{
            if(st[nodo].ultimo){
                valu[l] = min(valu[l], st[nodo].bajo);
                valu[l] = max(valu[l], st[nodo].alto);
            }
            else{
                valu[l] = max(valu[l], st[nodo].alto);
                valu[l] = min(valu[l], st[nodo].bajo);
            }
        }
    }
    else{
        if((st[nodo].bajo != -1 && st[nodo].alto != -1 && st[nodo].ultimo) || st[nodo].alto == -1){
            if(!st[nodo * 2].lazy){
                st[nodo * 2] = {1, -1, st[nodo].bajo, 0};
            }
            else{
                if(st[nodo * 2].bajo > st[nodo].bajo || st[nodo * 2].alto > st[nodo].bajo || st[nodo * 2].bajo == -1){
                    st[nodo * 2].ultimo = 0;
                    st[nodo * 2].bajo = st[nodo].bajo;
                }
            }
            if(!st[nodo * 2 + 1].lazy){
                st[nodo * 2 + 1] = {1, -1, st[nodo].bajo, 0};
            }
            else{
                if(st[nodo * 2 + 1].bajo > st[nodo].bajo || st[nodo * 2 + 1].alto > st[nodo].bajo || st[nodo * 2 + 1].bajo == -1){
                    st[nodo * 2 + 1].ultimo = 0;
                    st[nodo * 2 + 1].bajo = st[nodo].bajo;
                }
            }
            if(st[nodo].alto != -1){
                if(st[nodo * 2].alto < st[nodo].alto || st[nodo * 2].bajo > st[nodo].alto || st[nodo * 2].alto == -1){
                    st[nodo * 2].ultimo = 1;
                    st[nodo * 2].alto = st[nodo].alto;
                }
                if(st[nodo * 2 + 1].alto < st[nodo].alto || st[nodo * 2 + 1].bajo > st[nodo].alto || st[nodo * 2 + 1].alto == -1){
                    st[nodo * 2 + 1].ultimo = 1;
                    st[nodo * 2 + 1].alto = st[nodo].alto;
                }
            }
        }
        else{
            if(!st[nodo * 2].lazy){
                st[nodo * 2] = {1, st[nodo].alto, -1, 1};
            }
            else{
                if(st[nodo * 2].alto < st[nodo].alto || st[nodo * 2].bajo > st[nodo].alto || st[nodo * 2].alto == -1){
                    st[nodo * 2].ultimo = 1;
                    st[nodo * 2].alto = st[nodo].alto;
                }
            }
            if(!st[nodo * 2 + 1].lazy){
                st[nodo * 2 + 1] = {1, st[nodo].alto, -1, 1};
            }
            else{
                if(st[nodo * 2 + 1].alto < st[nodo].alto || st[nodo * 2 + 1].bajo > st[nodo].alto || st[nodo * 2 + 1].alto == -1){
                    st[nodo * 2 + 1].ultimo = 1;
                    st[nodo * 2 + 1].alto = st[nodo].alto;
                }
            }
            if(st[nodo].bajo != -1){
                if(st[nodo * 2].bajo > st[nodo].bajo || st[nodo * 2].alto > st[nodo].bajo || st[nodo * 2].bajo == -1){
                    st[nodo * 2].ultimo = 0;
                    st[nodo * 2].bajo = st[nodo].bajo;
                }
                if(st[nodo * 2 + 1].bajo > st[nodo].bajo || st[nodo * 2 + 1].alto > st[nodo].bajo || st[nodo * 2 + 1].bajo == -1){
                    st[nodo * 2 + 1].ultimo = 0;
                    st[nodo * 2 + 1].bajo = st[nodo].bajo;
                }
            }
        }
    }
    st[nodo] = {0, -1, -1, 0};
}

void built(int nodo, int l, int r){
    st[nodo] = {0, -1, -1, 0};
    if(l == r){
        return;
    }
    int mitad = (l + r) / 2;
    built(nodo * 2, l, mitad);
    built(nodo * 2 + 1, mitad + 1, r);
}

void update(int nodo, int l, int r, int a, int b, bool tipo, int val){
    push(nodo, l, r);
    if(r < a || l > b){
        return;
    }
    if(l >= a && r <= b){
        if(tipo){
            if(l == r){
                valu[l] = max(valu[l], val);
                return;
            }
            if(!st[nodo * 2].lazy){
                st[nodo * 2] = {1, val, -1, 1};
            }
            else{
                if(st[nodo * 2].alto < val || st[nodo * 2].bajo > val || st[nodo * 2].alto == -1){
                    st[nodo * 2].ultimo = 1;
                    st[nodo * 2].alto = val;
                }
            }
            if(!st[nodo * 2 + 1].lazy){
                st[nodo * 2 + 1] = {1, val, -1, 1};
            }
            else{
                if(st[nodo * 2 + 1].alto < val || st[nodo * 2 + 1].bajo > val || st[nodo * 2 + 1].alto == -1){
                    st[nodo * 2 + 1].ultimo = 1;
                    st[nodo * 2 + 1].alto = val;
                }
            }
            return;
        }
        else{
            if(l == r){
                valu[l] = min(valu[l], val);
                return;
            }
            if(!st[nodo * 2].lazy){
                st[nodo * 2] = {1, -1, val, 0};
            }
            else{
                if(st[nodo * 2].bajo > val || st[nodo * 2].alto > val || st[nodo * 2].bajo == -1){
                    st[nodo * 2].ultimo = 0;
                    st[nodo * 2].bajo = val;
                }
            }
            if(!st[nodo * 2 + 1].lazy){
                st[nodo * 2 + 1] = {1, -1, val, 0};
            }
            else{
                if(st[nodo * 2 + 1].bajo > val || st[nodo * 2 + 1].alto > val || st[nodo * 2 + 1].bajo == -1){
                    st[nodo * 2 + 1].ultimo = 0;
                    st[nodo * 2 + 1].bajo = val;
                }
            }
            return;
        }
    }
    int mitad = (l + r) / 2;
    update(nodo * 2, l, mitad, a, b, tipo, val);
    update(nodo * 2 + 1, mitad + 1, r, a, b, tipo, val);
}

void query(int nodo, int l, int r){
    push(nodo, l, r);
    if(l == r){
        return;
    }
    int mitad = (l + r) / 2;
    query(nodo * 2, l, mitad);
    query(nodo * 2 + 1, mitad + 1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    built(1, 0, n - 1);
    for(int i = 0; i < k; ++ i){
        bool opcion = (op[i] == 1);
        update(1, 0, n - 1, left[i], right[i], opcion, height[i]);
    }
    query(1, 0, n - 1);
    for(int i = 0; i < n; ++ i){
        finalHeight[i] = valu[i];
    }
}

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