제출 #1008563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1008563		hotboy2703	벽 (IOI14_wall)	C++14	100 / 100	436 ms	64656 KiB

wall

#include "wall.h"

#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 5e5+100;
const ll INF = 1e9;
ll n,k;
namespace segtree{
    pll tree[MAXN*4];
    void build(ll id,ll l,ll r){
        tree[id] = MP(0,INF);
        if (l != r){
            ll mid = (l + r) >> 1;
            build(id<<1,l,mid);
            build(id<<1|1,mid+1,r);
        }
    }
    void update(ll id,ll l,ll r,ll i,pll v){
        if (l > i || r < i)return;
        if (l==r){
            tree[id] = v;
            return;
        }
        ll mid = (l + r) >> 1;
        update(id<<1,l,mid,i,v);
        update(id<<1|1,mid+1,r,i,v);
        if (tree[id<<1].fi > tree[id<<1|1].se){
            tree[id] = MP(tree[id<<1|1].se,tree[id<<1|1].se);
        }
        else if (tree[id<<1|1].fi > tree[id<<1].se){
            tree[id] = MP(tree[id<<1|1].fi,tree[id<<1|1].fi);
        }
        else{
            tree[id].fi = max(tree[id<<1].fi,tree[id<<1|1].fi);
            tree[id].se = min(tree[id<<1].se,tree[id<<1|1].se);
        }
//        cout<<"SUS "<<id<<' '<<l<<' '<<r<<' '<<tree[id].fi<<' '<<tree[id].se<<'\n';
    }
    void update(ll i,pll v){
//        cout<<i<<' '<<v.fi<<' '<<v.se<<'\n';
        update(1,1,k,i,v);
    }
}
struct query{
    ll time,type,h,x,ins;
};
vector <query> all;

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
    n=N,k=K;
    for (ll i = 0;i < k;i ++){
        all.push_back({i+1,op[i],height[i],left[i],true});
        all.push_back({i+1,op[i],height[i],right[i]+1,false});
    }
    sort(all.begin(),all.end(),[&](query a,query b){return a.x < b.x;});
//    cout<<"SUS "<<all[0].x<<endl;
    using namespace segtree;
    build(1,1,k);
    for (ll i = 0,ptr = 0;i < n;i ++){
        while (ptr<sz(all) && all[ptr].x==i){
            query tmp = all[ptr];
            if (tmp.ins){
                pll rg;
                if (tmp.type==1)rg = MP(tmp.h,INF);
                else rg = MP(0,tmp.h);
                update(tmp.time,rg);
            }
            else{
                update(tmp.time,MP(0,INF));
            }
            ptr++;
        }
//        cout<<i<<' '<<tree[1].fi<<'\n';
        finalHeight[i] = tree[1].fi;
    }
    return;
}

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