제출 #994396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
994396		Alfraganus	벽 (IOI14_wall)	C++17	0 / 100	86 ms	11204 KiB

wall

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

#define print(a) for(auto x : a) cout << x << ' '; cout << endl;

struct SegTree {

    int size = 1;
    vector<int> mins, maxs;

    SegTree (int n){
        while(size < n)
            size <<= 1;
        mins.resize(2 * size, -1);
        maxs.resize(2 * size, -1);
    }

    void add(int l,  int r, int v, int x, int lx, int rx, int lastmin = -1, int lastmax = -1){
        if(maxs[x] != -1){
            if(maxs[x] <= v){
                if(lastmax == -1)
                    lastmax = maxs[x];
                else
                    lastmax = min(lastmax, maxs[x]);
                maxs[x] = -1;
            }
        }
        if(mins[x] != -1){
            if(mins[x] >= v and (lastmax == -1 or lastmax == v))
                return;
            lastmin = max(lastmin, mins[x]);
            mins[x] = -1;
        }
        if(l <= lx and rx <= r){
            mins[x] = max(mins[x], v);
            if(maxs[x] != -1)
                maxs[x] = max(maxs[x], mins[x]);
            return;
        }
        if(r <= lx or rx <= l){
            if(lastmin != -1){
                mins[x] = max(mins[x], lastmin);
                if(maxs[x] != -1)
                    maxs[x] = max(maxs[x], mins[x]);
            }
            if(lastmax != -1){
                if(maxs[x] == -1)
                    maxs[x] = lastmax;
                else
                    maxs[x] = min(maxs[x], lastmax);
            }
            return;
        }
        int mid = (lx + rx) >> 1;
        add(l, r, v, (x << 1) + 1, lx, mid, lastmin, lastmax);
        add(l, r, v, (x << 1) + 2, mid, rx, lastmin, lastmax);
    }

    void add(int l, int r, int v){
        add(l, r, v, 0, 0, size);
    }

    void remove(int l, int r, int v, int x, int lx, int rx, int lastmin = -1, int lastmax = -1){
        if(maxs[x] != -1){
            if(maxs[x] <= v)
                return;
            if(lastmax == -1)
                lastmax = maxs[x];
            else
                lastmax = min(lastmax, maxs[x]);
            maxs[x] = -1;
        }
        if(mins[x] != -1){
            if(mins[x] <= v){
                lastmin = max(lastmin, mins[x]);
                mins[x] = -1;
            }
        }
        if(l <= lx and rx <= r){
            if(maxs[x] == -1)
                maxs[x] = v;
            else
                maxs[x] = min(maxs[x], v);
            if(mins[x] != -1)
                mins[x] = min(mins[x], maxs[x]);
            return;
        }
        if(rx <= l or r <= lx){
            if(lastmax != -1){
                maxs[x] = min(maxs[x], lastmax);
                if(mins[x] != -1)
                    mins[x] = min(mins[x], maxs[x]);
            }
            if(lastmin != -1){
                mins[x] = max(mins[x], lastmin);
                if(mins[x] != -1)
                    mins[x] = min(mins[x], maxs[x]);
            }
            return;
        }
        int mid = (lx + rx) >> 1;
        remove(l, r, v, (x << 1) + 1, lx, mid, lastmin, lastmax);
        remove(l, r, v, (x << 1) + 2, mid, rx, lastmin, lastmax);
    }

    void remove(int l, int r, int v){
        remove(l, r, v, 0, 0, size);
    }

    int query(int ind, int x, int l, int r){
        if(l + 1 == r){
            if(mins[x] == -1)
                return 0;
            return mins[x];
        }
        int mid = (l + r) >> 1;
        int ans = -1;
        if(ind < mid)
            ans = query(ind, (x << 1) + 1, l, mid);
        else
            ans = query(ind, (x << 1) + 2, mid, r);
        int left = max(0, mins[x]), right = (maxs[x] == -1 ? 1e9 : maxs[x]);
        if(left <= ans and ans <= right)
            return ans;
        else if(ans < left)
            return left;
        return right;
    }

    int query(int x){
        return query(x, 0, 0, size);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SegTree s(n);
    for(int i = 0; i < k; i ++){
        if(op[i] == 1)
            s.add(left[i], right[i] + 1, height[i]);
        else
            s.remove(left[i], right[i] + 1, height[i]);
    }
    for(int i = 0; i < n; i ++)
        finalHeight[i] = s.query(i);
}

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