Submission #730386

#	Time	Username	Problem	Language	Result	Execution time	Memory
730386		murad_2005	Wall (IOI14_wall)	C++17	100 / 100	594 ms	69560 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"
#define ll long long
#define INF 1e9

using namespace std;

const int up = 2e6 + 3;

struct node{
    int Min, Max;

    node(){

    }
    node(int mn, int mx){
        mn = Min, mx = Max;
    }
};

node st[up << 2];

void build(int v, int l, int r){
    if(l == r){
        st[v] = node(0, INF);
    }else{
        int mid = (l + r) >> 1;
        build(v << 1, l, mid);
        build((v << 1) | 1, mid + 1, r);
    }
}

void push(int v){
    st[v << 1].Min = min(st[v].Max, max(st[v << 1].Min, st[v].Min));
    st[v << 1].Max = max(st[v].Min, min(st[v << 1].Max, st[v].Max));

    st[(v << 1) | 1].Min = min(st[v].Max, max(st[(v << 1) | 1].Min, st[v].Min));
    st[(v << 1) | 1].Max = max(st[v].Min, min(st[(v << 1) | 1].Max, st[v].Max));

    st[v].Min = 0;
    st[v].Max = INF;
}

void update(int v, int l, int r, int ul, int ur, int op, int h){
    if(ur < l || r < ul) return;
    else if(ul <= l && r <= ur){
        if(op == 1){ // add
            st[v].Min = max(st[v].Min, h);
            st[v].Max = max(st[v].Max, h);
        }else{ // remove
            st[v].Max = min(st[v].Max, h);
            st[v].Min = min(st[v].Min, h);
        }
    }else{
        push(v);
        int mid = (l + r) >> 1;
        update(v << 1, l, mid, ul, ur, op, h);
        update((v << 1) | 1, mid + 1, r, ul, ur, op, h);
    }
}

void query(int v, int l, int r, int finalHeight[]){
    if(l == r){
        finalHeight[l - 1] = st[v].Min;
    }else{
        push(v);
        int mid = (l + r) >> 1;
        query(v << 1, l, mid, finalHeight);
        query((v << 1) | 1, mid + 1, r, finalHeight);
    }
}

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

Compilation message (stderr)

wall.cpp: In constructor 'node::node(int, int)':
wall.cpp:17:12: warning: '*<unknown>.node::Min' is used uninitialized in this function [-Wuninitialized]
   17 |         mn = Min, mx = Max;
      |         ~~~^~~~~
wall.cpp:17:22: warning: '*<unknown>.node::Max' is used uninitialized in this function [-Wuninitialized]
   17 |         mn = Min, mx = Max;
      |                   ~~~^~~~~

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