제출 #700249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
700249		boyliguanhan	벽 (IOI14_wall)	C++17	61 / 100	561 ms	16400 KiB

wall

#include <iostream>
#include<algorithm>
#define M 0xfffff
#include "wall.h"
using namespace std;
struct seg {
    int v, l, r, lzmn, lzmx;
} t[2000100];
void build(int i, int l, int r) {
    t[i] = { 0, l, r, M, 0 };
    if (l ^ r)
        build(i * 2, l, l + r >> 1), build(i * 2 + 1, l + r + 2 >> 1, r);
}
void cmn(int i, int v) {
    t[i].lzmn = min(t[i].lzmn, v);
    t[i].lzmx = min(t[i].lzmx, v);
}
void cmx(int i, int v) {
    t[i].lzmn = max(t[i].lzmn, v);
    t[i].lzmx = max(t[i].lzmx, v);
}
void pd(int i) {
    if (t[i].lzmn != M) {
        if (t[i].l != t[i].r)
            cmn(i * 2, t[i].lzmn), cmn(i * 2 + 1, t[i].lzmn);
        else
            t[i].v = min(t[i].v, t[i].lzmn);
        t[i].lzmn = M;
    }
    if (t[i].lzmx) {
        if (t[i].l != t[i].r)
            cmx(i * 2, t[i].lzmx), cmx(i * 2 + 1, t[i].lzmx);
        else
            t[i].v = max(t[i].v, t[i].lzmx);
        t[i].lzmx = 0;
    }
}
void umn(int i, int l, int r, int v) {
    if (l <= t[i].l && t[i].r <= r) {
        cmn(i, v);
        return;
    }
    pd(i);
    if (t[i * 2].r < r)
        umn(i * 2 + 1, l, r, v);
    if (l <= t[i * 2].r)
        umn(i * 2, l, r, v);
}
void umx(int i, int l, int r, int v) {
    if (l <= t[i].l && t[i].r <= r) {
        cmx(i, v);
        return;
    }
    pd(i);
    if (t[i * 2].r < r)
        umx(i * 2 + 1, l, r, v);
    if (l <= t[i * 2].r)
        umx(i * 2, l, r, v);
}
int query(int i, int x) {
    pd(i);
    if (t[i].l == t[i].r)
        return t[i].v;
    if (t[i * 2].r < x)
        return query(i * 2 + 1, x);
    return query(i * 2, x);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    build(1, 0, n-1);
    for (int i = 0; i < k; i++) {
        (op[i]==1?umx:umn)(1, left[i], right[i], height[i]);
    }
    for (int i = 0; i < n; i++)
        finalHeight[i] = query(1, i);
}

컴파일 시 표준 에러 (stderr) 메시지

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:13:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |         build(i * 2, l, l + r >> 1), build(i * 2 + 1, l + r + 2 >> 1, r);
      |                         ~~^~~
wall.cpp:13:61: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |         build(i * 2, l, l + r >> 1), build(i * 2 + 1, l + r + 2 >> 1, r);
      |                                                       ~~~~~~^~~

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