제출 #795794

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
795794		chanhchuong123	Wall (IOI14_wall)	C++14	100 / 100	546 ms	72844 KiB

wall

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

const int INF = 1e9 + 7;
const int MAX = 2000020;
int n, ans[MAX];

struct segtree {
    pair<int, int> st[MAX << 2];

    void build(int id, int l, int r) {
        st[id] = make_pair(-INF, INF);
        if (l == r) {
            st[id] = make_pair(0, 0);
            return;
        }
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }

    void update(int id, int l, int r) {
        if (st[id].first > r) st[id] = make_pair(r, r); else
        if (st[id].second < l) st[id] = make_pair(l, l); else
        st[id] = make_pair(max(l, st[id].first), min(r, st[id].second));
    }

    void push(int id) {
        update(id << 1, st[id].first, st[id].second);
        update(id << 1 | 1, st[id].first, st[id].second); st[id] = make_pair(-INF, INF);
    }

    void update(int id, int l, int r, int u, int v, int t, int newH) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            if (!t) update(id, newH, INF);
            else update(id, -INF, newH);
            return;
        }
        int mid = l + r >> 1; push(id);
        update(id << 1, l, mid, u, v, t, newH);
        update(id << 1 | 1, mid + 1, r, u, v, t, newH);
    }

} tree;

void magic(int id, int l, int r) {
    if (l == r) {
        ans[l] = tree.st[id].first;
        return;
    }
    int mid = l + r >> 1; tree.push(id);
    magic(id << 1, l, mid); magic(id << 1 | 1, mid + 1, r);
}

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

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

wall.cpp: In member function 'void segtree::build(int, int, int)':
wall.cpp:18:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |         int mid = l + r >> 1;
      |                   ~~^~~
wall.cpp: In member function 'void segtree::update(int, int, int, int, int, int, int)':
wall.cpp:41:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int mid = l + r >> 1; push(id);
      |                   ~~^~~
wall.cpp: In function 'void magic(int, int, int)':
wall.cpp:53:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     int mid = l + r >> 1; tree.push(id);
      |               ~~^~~

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