oj.uz

Submission #730386

# Submission time Handle Problem Language Result Execution time Memory
730386 2023-04-25T19:25:43 Z murad_2005 Wall (IOI14_wall) C++17
100 / 100
 594 ms 69560 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 122 ms 8068 KB Output is correct
3 Correct 132 ms 4172 KB Output is correct
4 Correct 373 ms 20308 KB Output is correct
5 Correct 250 ms 21480 KB Output is correct
6 Correct 250 ms 19788 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 5 ms 748 KB Output is correct
6 Correct 5 ms 700 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 136 ms 13900 KB Output is correct
9 Correct 139 ms 7912 KB Output is correct
10 Correct 374 ms 20344 KB Output is correct
11 Correct 242 ms 21368 KB Output is correct
12 Correct 263 ms 19812 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 136 ms 13852 KB Output is correct
15 Correct 23 ms 2012 KB Output is correct
16 Correct 351 ms 20644 KB Output is correct
17 Correct 243 ms 20060 KB Output is correct
18 Correct 246 ms 20012 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 4 ms 708 KB Output is correct
6 Correct 4 ms 704 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 128 ms 13864 KB Output is correct
9 Correct 148 ms 7908 KB Output is correct
10 Correct 384 ms 20304 KB Output is correct
11 Correct 253 ms 21380 KB Output is correct
12 Correct 241 ms 19896 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 180 ms 13924 KB Output is correct
15 Correct 22 ms 1956 KB Output is correct
16 Correct 369 ms 20620 KB Output is correct
17 Correct 310 ms 19996 KB Output is correct
18 Correct 246 ms 20024 KB Output is correct
19 Correct 573 ms 69560 KB Output is correct
20 Correct 564 ms 67024 KB Output is correct
21 Correct 560 ms 69484 KB Output is correct
22 Correct 594 ms 66916 KB Output is correct
23 Correct 591 ms 66912 KB Output is correct
24 Correct 563 ms 67016 KB Output is correct
25 Correct 564 ms 67032 KB Output is correct
26 Correct 577 ms 69452 KB Output is correct
27 Correct 576 ms 69512 KB Output is correct
28 Correct 580 ms 67016 KB Output is correct
29 Correct 567 ms 67024 KB Output is correct
30 Correct 564 ms 67036 KB Output is correct