Submission #58631

#	Time	Username	Problem	Language	Result	Execution time	Memory
58631		RezwanArefin01	벽 (IOI14_wall)	C++17	100 / 100	1185 ms	96904 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std; 

const int N = 2e6 + 10; 
int a[N], mn[N << 2], mx[N << 2]; 

void applymin(int node, int h) {
    mn[node] = min(mn[node], h);
    mx[node] = min(mx[node], mn[node]); 
}
void applymax(int node, int h) {
    mx[node] = max(mx[node], h); 
    mn[node] = max(mn[node], mx[node]); 
}
void shift(int node) {
    applymin(node << 1, mn[node]);
    applymin(node << 1 | 1, mn[node]); 
    applymax(node << 1, mx[node]); 
    applymax(node << 1 | 1, mx[node]);
    mx[node] = 0;
    mn[node] = INT_MAX; 
}
void update(int node, int l, int r, int op, int i, int j, int h) {
    if(r < i || l > j) return; 
    if(i <= l && r <= j) {
        if(op == 1) applymax(node, h); 
        else applymin(node, h); 
        return; 
    } shift(node); 
    int m = l + r >> 1; 
    update(node << 1, l, m, op, i, j, h); 
    update(node << 1 | 1, m + 1, r, op, i, j, h); 
}

void get(int node, int l, int r) {
    if(l == r) {
        a[l] = min(a[l], mn[node]); 
        a[l] = max(a[l], mx[node]); 
        return;
    } int m = l + r >> 1; 
    shift(node); 
    get(node << 1, l, m); 
    get(node << 1 | 1, m + 1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    fill(mn, mn + (n << 2), INT_MAX); 
    fill(mx, mx + (n << 2), 0); 
    for(int i = 0; i < k; i++) {
        update(1, 0, n - 1, op[i], left[i], right[i], height[i]); 
    } get(1, 0, n - 1); 
    for(int i = 0; i < n; i++) 
        finalHeight[i] = a[i];
}

Compilation message (stderr)

wall.cpp: In function 'void update(int, int, int, int, int, int, int)':
wall.cpp:31:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~
wall.cpp: In function 'void get(int, int, int)':
wall.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     } int m = l + r >> 1; 
               ~~^~~

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