제출 #301652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
301652		kevinsogo	벽 (IOI14_wall)	C++17	100 / 100	1139 ms	224676 KiB

wall

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

const int INF = 1 << 30;

struct window {
    int l, r;
    window(int l = -INF, int r = +INF): l(l), r(r) {
        assert(l <= r);
    }

    window operator*(const window& o) const {
        window w = *this; w *= o; return w;
    }

    window& operator*=(const window& o) {
        l = o(l); r = o(r);
        return *this;
    }

    int operator()(int v) const {
        return clamp(v, l, r);
    }
};

struct Tree {
    int i, j;
    window v;
    Tree *l, *r;
    Tree(int i, int j): i(i), j(j) {
        if (j - i == 1) {
            v = window(0, 0);
            l = r = nullptr;
        } else {
            int k = i + j >> 1;
            l = new Tree(i, k);
            r = new Tree(k, j);
        }
    }

    void visit() {
        if (l) {
            l->v *= v;
            r->v *= v;
            v = window();
        }
    }

    void chop(int I, int J, const window& w) {
        if (I <= i && j <= J) {
            v *= w;
            visit();
        } else {
            visit();
            if (!(J <= i || j <= I)) {
                l->chop(I, J, w);
                r->chop(I, J, w);
            }
        }
    }

    int *trav(int *t) {
        visit();
        if (l) {
            t = l->trav(t);
            t = r->trav(t);
        } else {
            assert(v.l == v.r);
            *(t++) = v.l;
        }
        return t;
    }
};

#define LW 1
#define HG 2

void buildWall(int n, int q, int ops[], int lfs[], int rgs[], int hts[], int finalHeight[]) {
    Tree t(0, n);
    for (int qq = 0; qq < q; qq++) {
        t.chop(lfs[qq], ++rgs[qq], ops[qq] == LW ? window(hts[qq], INF) : window(-INF , hts[qq]));
    }
    t.trav(finalHeight);
}

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

wall.cpp: In constructor 'Tree::Tree(int, int)':
wall.cpp:36:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |             int k = i + j >> 1;
      |                     ~~^~~

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