Submission #566044

#	Time	Username	Problem	Language	Result	Execution time	Memory
566044		Leo121	Wall (IOI14_wall)	C++14	100 / 100	654 ms	77356 KiB

wall

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

#define for0(i, n) for(int i = 0; i < int(b); ++ i)
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef pair<int, int> pii;

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

void built(int nodo, int l, int r){
    st[nodo] = mp(0, 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){
    if(l != r && st[nodo].fi == st[nodo].se){
        st[nodo * 2] = st[nodo];
        st[nodo * 2 + 1] = st[nodo];
    }
    if(r < a || l > b){
        return;
    }
    if(l >= a && r <= b){
        if(tipo){
            if(st[nodo].se >= val){
                return;
            }
            if(st[nodo].fi < val){
                st[nodo] = mp(val, val);
                return;
            }
        }
        else{
            if(st[nodo].fi <= val){
                return;
            }
            if(st[nodo].se > val){
                st[nodo] = mp(val, 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);
    st[nodo] = mp(max(st[nodo * 2].fi, st[nodo * 2 + 1].fi), min(st[nodo * 2].se, st[nodo * 2 + 1].se));
}

void query(int nodo, int l, int r){
    if(st[nodo].fi == st[nodo].se){
        forn(i, l, r){
            valu[i] = st[nodo].fi;
        }
        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: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39