Submission #1133143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133143		t9unkubj	벽 (IOI14_wall)	C++20	0 / 100	146 ms	23880 KiB

wall

#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
template<class T>
struct dual_seg{
    int n;
    using F=function<T(T,T)>;
    F op;
    T id;
    vector<T>lazy;
    int log=0;
    dual_seg(int n_,F op,T id):n(n_),op(op),id(id){
        while((1<<log)<n_)log++;
        n=1<<log;
        lazy=vector<T>(n*2,id);
    }
    void set(int i,T x){
        assert(0<=i&&i<n);
        for(int j=log;j>=1;j--){
            push(i>>j);
        }
        lazy[i]=x;
    }
    void apply(int l,int r,T x){
        assert(0<=l&&l<=r&&r<=n);
        if(l==r)return;
        l+=n,r+=n;
        for(int i=log;i>=1;i--){
            if(((l>>i)<<i)!=l)push(l>>i);
            if(((r>>i)<<i)!=r)push((r-1)>>i);
        }
        while(l<r){
            if(l&1)all_apply(l++,x);
            if(r&1)all_apply(--r,x);
            l>>=1,r>>=1;
        }
    }
    T get(int i){
        assert(0<=i&&i<n);
        i+=n;
        for(int j=log;j>=1;j--){
            push(i>>j);
        }
        return lazy[i];
    }
    void push(int k){
        all_apply(k*2,lazy[k]),all_apply(k*2+1,lazy[k]);
        lazy[k]=id;
    }
    void all_apply(int k,T x){
        lazy[k]=op(lazy[k],x);
    }
};
struct S{
    ll low;
    ll high;
    //[low,high]
};

vc<int>solve(int n,int k,vc<int>op,vc<int>l,vc<int>r,vc<int>h){

    dual_seg<S>seg(n,[&](auto a,auto b){
        S c;
        c.low=max(b.low,min(a.low,a.high));
        c.high=min(b.high,max(c.low,a.high));
        return c;
    },S{(ll)-2e18,(ll)2e18});
    rep(i,k){
        if(op[i]==1){
            seg.apply(l[i],r[i]+1,S{h[i],(ll)2e18});
        }else{
            seg.apply(l[i],r[i]+1,S{0,h[i]});
        }
    }
    vc<int>ans(n);
    rep(i,n){
        auto R=seg.get(i);
        ans[i]=clamp<ll>(0,R.low,R.high);
    }
    return ans;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    vc<int>OP(k),l(k),r(k),h(k);
    rep(i,k)OP[i]=op[i],l[i]=left[i],r[i]=right[i],h[i]=height[i];
    auto res=solve(n,k,OP,l,r,h);
    rep(i,n)finalHeight[i]=res[i];
}
namespace judge{
    void run(){
        int n,k;
        cin>>n>>k;
        int op[k],l[k],r[k],h[k];
        int ans[n];
        rep(i,k)cin>>op[i]>>l[i]>>r[i]>>h[i];
        buildWall(n,k,op,l,r,h,ans);
        rep(i,n)dbg(ans[i]);
    }
};
//int main(){judge::run();}

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