제출 #374870

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
374870		Alex_tz307	벽 (IOI14_wall)	C++17	100 / 100	1171 ms	114700 KiB

wall

#include <bits/stdc++.h>
 
using namespace std;
 
struct Segtree {
    int Size;
    vector<pair<int,int>> tree;
    vector<pair<bool,int>> lazy_min, lazy_max;
 
    void init(int N) {
        Size = 1;
        while(Size < N)
            Size <<= 1;
        tree.assign((Size << 1) + 1, make_pair(INT_MAX, 0));
        lazy_min.assign((Size << 1) + 1, make_pair(false, INT_MAX));
        lazy_max.assign((Size << 1) + 1, make_pair(false, 0));
    }
 
    void propagate(int x, int lx, int rx) {
        if(lx == rx)
            return;
        if(lazy_min[x].first) {
            tree[x << 1].first = min(tree[x << 1].first, lazy_min[x].second);
            tree[(x << 1) | 1].first = min(tree[(x << 1) | 1].first, lazy_min[x].second);
            tree[x << 1].second = min(tree[x << 1].first, tree[x << 1].second);
            tree[(x << 1) | 1].second = min(tree[(x << 1) | 1].first, tree[(x << 1) | 1].second);
            lazy_min[x << 1].first = lazy_min[(x << 1) | 1].first = true;
            lazy_min[x << 1].second = min(lazy_min[x << 1].second, lazy_min[x].second);
            lazy_min[(x << 1) | 1].second = min(lazy_min[(x << 1) | 1].second, lazy_min[x].second);
            if(lazy_max[x << 1].first)
                lazy_max[x << 1].second = min(lazy_min[x << 1].second, lazy_max[x << 1].second);
            if(lazy_max[(x << 1) | 1].first)
                lazy_max[(x << 1) | 1].second = min(lazy_min[(x << 1) | 1].second, lazy_max[(x << 1) | 1].second);
            lazy_min[x] = make_pair(false, INT_MAX);
        }
        if(lazy_max[x].first) {
            tree[x << 1].second = max(tree[x << 1].second, lazy_max[x].second);
            tree[(x << 1) | 1].second = max(tree[(x << 1) | 1].second, lazy_max[x].second);
            tree[x << 1].first = max(tree[x << 1].first, tree[x << 1].second);
            tree[(x << 1) | 1].first = max(tree[(x << 1) | 1].first, tree[(x << 1) | 1].second);
            lazy_max[x << 1].first = lazy_max[(x << 1) | 1].first = true;
            lazy_max[x << 1].second = max(lazy_max[x << 1].second, lazy_max[x].second);
            lazy_max[(x << 1) | 1].second = max(lazy_max[(x << 1) | 1].second, lazy_max[x].second);
            if(lazy_min[x << 1].first)
                lazy_min[x << 1].second = max(lazy_min[x << 1].second, lazy_max[x << 1].second);
            if(lazy_min[(x << 1) | 1].first)
                lazy_min[(x << 1) | 1].second = max(lazy_min[(x << 1) | 1].second, lazy_max[(x << 1) | 1].second);
            lazy_max[x] = make_pair(false, 0);
        }
    }
 
    void maximize(int x, int lx, int rx, int st, int dr, int h) {
        propagate(x, lx, rx);
        if(st <= lx && rx <= dr) {
            tree[x].second = max(tree[x].second, h);
            tree[x].first = max(tree[x].first, tree[x].second);
            lazy_max[x].first = true;
            lazy_max[x].second = max(lazy_max[x].second, h);
            return;
        }
        int mid = (lx + rx) >> 1;
        if(st <= mid)
            maximize(x << 1, lx, mid, st, dr, h);
        if(mid < dr)
            maximize((x << 1) | 1, mid + 1, rx, st, dr, h);
    }
 
    void minimize(int x, int lx, int rx, int st, int dr, int h) {
        propagate(x, lx, rx);
        if(st <= lx && rx <= dr) {
            tree[x].first = min(tree[x].first, h);
            tree[x].second = min(tree[x].second, tree[x].first);
            lazy_min[x].first = true;
            lazy_min[x].second = min(lazy_min[x].second, h);
            return;
        }
        int mid = (lx + rx) >> 1;
        if(st <= mid)
            minimize(x << 1, lx, mid, st, dr, h);
        if(mid < dr)
            minimize((x << 1) | 1, mid + 1, rx, st, dr, h);
    }
 
    int query(int x, int lx, int rx, int poz) {
        propagate(x, lx, rx);
        if(lx == rx)
            return tree[x].second;
        int mid = (lx + rx) >> 1;
        if(poz <= mid)
            return query(x << 1, lx, mid, poz);
        else
            return query((x << 1) | 1, mid + 1, rx, poz);
    }
};
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    Segtree tree;
    tree.init(n);
    for(int i = 0; i < k; ++i) 
        if(op[i] == 1)
            tree.maximize(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
        else
            tree.minimize(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
    for(int i = 0; i < n; ++i)
        finalHeight[i] = tree.query(1, 1, n, i + 1);
}

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