oj.uz

Submission #730382

# Submission time Handle Problem Language Result Execution time Memory
730382 2023-04-25T19:15:00 Z murad_2005 Wall (IOI14_wall) C++14
0 / 100
 138 ms 13908 KB 
#include<bits/stdc++.h>
#include "wall.h"
#define ll long long
#define INF 1e9

using namespace std;

const int up = 2e6;

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(2 * v + 1, l, mid);
        build(2 * v + 2, mid + 1, r);
    }
}

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

    st[2 * v + 2].Min = min(st[v].Max, max(st[2 * v + 2].Min, st[v].Min));
    st[2 * v + 2].Max = max(st[v].Min, min(st[2 * v + 2].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) / 2;
        update(2 * v + 1, l, mid, ul, ur, op, h);
        update(2 * v + 2, mid + 1, r, ul, ur, op, h);
    }
}

int query(int v, int l, int r, int in){
    if(l == r){
        return st[v].Min;
    }else{
        push(v);
        int mid = (l + r) / 2;
        if(in < mid) return query(2 * v + 1, l, mid, in);
        else return query(2 * v + 2, mid + 1, r, in);
    }
}

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

Compilation message

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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 125 ms 13908 KB Output is correct
3 Incorrect 138 ms 7852 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Incorrect 2 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Incorrect 2 ms 368 KB Output isn't correct
4 Halted 0 ms 0 KB -