제출 #395145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395145		jeroenodb	벽 (IOI14_wall)	C++14	100 / 100	761 ms	92100 KiB

wall

#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
int* pt;
struct segtree {
    int n, ptwo;
    struct Node {
        // Change here the values you want to propagate, and store
        int mn =0, mx = 100000;
        int l,r;
        Node () {}
        Node(int i) {
            l = r = i;
        }
    };
    vector<Node> d;
    void set(int i, int mn, int mx) {
        Node& rc = d[i];
        rc.mn = max(mn,rc.mn);
        rc.mx = min(mx,rc.mx);
        if(rc.mn>rc.mx) {
            if(mn>rc.mx) rc.mx = rc.mn;
            else rc.mn = rc.mx;
        }
    }
    void push(int i) {
        // Pushes the propagation values down to the children
        set(2*i, d[i].mn, d[i].mx);
        set(2*i+1, d[i].mn, d[i].mx);
        d[i].mn = 0; d[i].mx = 100000;
    }
    segtree(int _n) {
        n = _n;
        ptwo= 1;
        while(ptwo<n) ptwo*=2;
        d.resize(2*ptwo);
        for(int i=ptwo;i<ptwo*2;++i) {
            d[i] = Node(i-ptwo);
        }
        for(int i=ptwo-1;i>0;--i) {
            d[i].l = d[i*2].l; d[i].r = d[i*2+1].r;
        }
    }
    void query(int i=1, int mn = 0, int mx = 100000) {
        Node& c = d[i];
        if(c.l>=n) return;
        mn = max(mn,c.mn);
        mx = min(mx,c.mx);
        if(mn>mx) {
            if(c.mn>mx) mn = mx;
            else mx = mn;
        }
        if(c.l==c.r) {
            *pt = mn;
            pt++;
            return;
        }
        query(i*2,mn,mx);
        query(i*2+1,mn,mx);
    }
    void update(int l, int r, bool lower, int val, int i=1) {
        Node& c = d[i];
        if(c.l < l or r < c.r ) {
            push(i);
            int mid = (c.r+c.l)/2;
            if(l<=mid) {
                update(l,r,lower,val,i*2);
            }
            if(r>mid) {
                update(l,r,lower,val,i*2+1);
            }
        } else {
            if(!lower) {
                c.mn = max(val,c.mn);
                if(c.mn>c.mx) c.mx = c.mn;
            } else {
                c.mx = min(val,c.mx);
                if(c.mn>c.mx) c.mn = c.mx;
            }
        }
    }

};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    segtree seg(n);
    pt = finalHeight;
    for(int i=0;i<k;++i) {
        seg.update(left[i],right[i], op[i]==2, height[i]);
    }
    seg.query();
}

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